样例过了,提交后全wa,下载数据1发现居然就跟样例一样的,但是提交了好几次,明明样例对的就是不让过,求调
#include<bits/stdc++.h>
//#define int long long
#define endl "\n"
using namespace std;
int n,c;
int dis[60],w[60];
int dp[60][60][3];//dp[i][j][k]表示关掉i到j的路灯且最后站在i或j的位置(k=0时站在i,k=1时站在j)时的最小功率
signed main()
{
ios::sync_with_stdio(0);
scanf("%d%d",&n,&c);
memset(dp,0x3f,sizeof(dp));
for(int i=1;i<=n;++i)
{
cin>>dis[i];
cin>>w[i];
w[i]+=w[i-1];//功率前缀和 ,距离因为是给的位置,已经是前缀和了
}
dp[c][c][0]=dp[c][c][1]=0;//人站在中途的起点时dp为0,初始化
for(int len=2;len<=n;++len)//枚举长度
{
for(int i=1;i+len-1<=n;++i)//枚举i
{
int j=i+len-1;
//一下dp方程中的dis...*w...就是指路灯间的距离(因为速度为1,所以距离就为时间)乘上功率,就是所花的功率
dp[i][j][0]=min(dp[i+1][j][0]+(dis[i+1]-dis[i])*(w[i])+(w[n]-w[j])*(dis[i+1]-dis[i]),dp[i+1][j][1]+(dis[j]-dis[i])*(w[n]-w[j])+(w[i])*(dis[j]-dis[i]));
dp[i][j][1]=min(dp[i][j-1][1]+(dis[j]-dis[j-1])*(w[i-1])+(dis[j]-dis[j-1])*(w[n]-w[j-1]),dp[i][j-1][0]+(dis[j]-dis[i])*(w[n]-w[j-1])+(dis[j]-dis[i])*(w[i-1]));
}
}
cout<<min(dp[1][n][0],dp[1][n][1]);//求最小值
return 0;
}