问一个可能很智障的问题
查看原帖
问一个可能很智障的问题
195331
Mine_KingCattleya楼主2021/3/14 20:50

这题 dfs 时题解里的各位大佬都用了一个数组先记录 f 数组,比如这样:

memcpy(tmp,f[u],sizeof(f[u]));
		memset(f[u],0x3f,sizeof(f[u]));
		for(int j=0;j<=k;++j){
			for(int t=0;t<=j;++t){
				f[u][j][0]=min(f[u][j][0],min(f[v][t][0]+tmp[j-t][0]+(m==2)*w,f[v][t][1]+tmp[j-t][0]));
				f[u][j][1]=min(f[u][j][1],min(f[v][t][1]+tmp[j-t][1]+w,f[v][t][0]+tmp[j-t][1]));
			}
		}

这是第二篇题解的代码。
写题解的大佬说这么处理的原因是

这题在更新f[u][j]的时候会被f[u][j-t]更新,所以这个东西就开始自己自己了……

那么,为什么不能像 01 背包那样倒序枚举呢?比如这样:

for(int j=k;j>=0;j--)
				for(int t=j;t>=0;t--)
				{
					dp[now][j][0]=min(dp[now][j][0],min(dp[v][t][0]+dp[now][j-t][0]+(m==2)*w,dp[v][t][1]+dp[now][j-t][0]));
					dp[now][j][1]=min(dp[now][j][1],min(dp[v][t][0]+dp[now][j-t][1],dp[v][t][1]+dp[now][j-t][1]+w));
				}

实践之后发现连样例都过不了dk,输出0

求大佬解答为啥不能这样做kel

2021/3/14 20:50
加载中...