这题 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));
}
实践之后发现连样例都过不了,输出0
求大佬解答为啥不能这样做