求助dp顺序
查看原帖
求助dp顺序
346383
q779楼主2022/6/7 17:44

请问为什么下面那一种写法不对呢?

下面的写法样例跑出来是42

// AC
for(int j=m,t; j>=0; j--)
{
    t=-INF;
    for(int k=0; k<=j; k++)
        t=max(t,g[j-k]+f[v][l*w][k]);
    g[j]=t;
}

// WA
for(int j=0; j<=m; j++)
    tmp[j]=g[j];
for(int j=0; j<=m; j++)
    for(int k=0; j+k<=m; k++)
        g[j+k]=max(g[j+k],tmp[j]+f[v][l*w][k]);

完整代码

2022/6/7 17:44
加载中...