for(int i=0;i<=n;i++)
for(int j=0;j<N;j++)//就是这里
f[i][j][0]=f[i][j][1]=INF;
f[n][0][0]=f[n][1][1]=0;
for(int i=n-1;i>=1;i--)
for(int j=0;j<=n-i+1;j++)
{
f[i][j][0]=min(dis[c[i]][c[i+1]]+f[i+1][j][0],dis[c[i]][d[i+1]]*k[i+1]+dis[c[i]][c[i+1]]*(1-k[i+1])+f[i+1][j][1]);
if(j==0) continue;
f[i][j][1]=min(f[i][j][1],dis[c[i]][c[i+1]]*(1-k[i])+dis[d[i]][c[i+1]]*k[i]+f[i+1][j-1][0]);
f[i][j][1]=min(f[i][j][1],dis[c[i]][c[i+1]]*(1-k[i+1])*(1-k[i])+dis[d[i]][c[i+1]]*k[i]*(1-k[i+1])+dis[c[i]][d[i+1]]*(1-k[i])*k[i+1]+dis[d[i]][d[i+1]]*k[i]*k[i+1]+f[i+1][j-1][1]);
}
double ans=2000000000;
for(int i=0;i<=m;i++)
ans=min(ans,min(f[1][i][0],f[1][i][1]));
这个代码的DP是正确的,但是初始化那里出了点问题。如果将j弄到最大(N就是数组的大小),就是对的。但是如果将这个句子改为
for(int j=0;j<=n-i+1;j++)
即跟DP的时候的状态量一样就会错误,答案就会变小。但是DP过程并没用到大于这个临界值(n−i+1)的dp值,按理来说应该不会影响答案啊?请问我哪里错了,谢谢。
ps.最后变小的答案并不为0