蒟蒻求助代码细节
查看原帖
蒟蒻求助代码细节
65190
_LanFeng_楼主2021/9/10 21:37
        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是正确的,但是初始化那里出了点问题。如果将jj弄到最大(NN就是数组的大小),就是对的。但是如果将这个句子改为

for(int j=0;j<=n-i+1;j++)

即跟DP的时候的状态量一样就会错误,答案就会变小。但是DP过程并没用到大于这个临界值(ni+1n-i+1)的dp值,按理来说应该不会影响答案啊?请问我哪里错了,谢谢。

ps.最后变小的答案并不为0

2021/9/10 21:37
加载中...