多加一句话就wa啦就奇怪呀

P1509 找啊找啊找GF

是这样的: 你康,你关于f的转移方程为 ``` f[j][k] = f[j - rmb[i]][k - rp[i]] + ti[i]; f[j][k] = min(f[j][k], f[j - rmb[i]][k - rp[i]] + ti[i]); f[j][k] = f[j][k]; ``` 在这里面,第三条转移方程不管...自己等于自己 第一条与第二条,唯一存在的变数是 ``` f[j - rmb[i]][k - rp[i]] + ti[i] ``` 但是这玩意,与之前的值都已经被你赋值为**0x3f** 于是你有一条值: ``` f[m][r] = 0; ``` 在这之前,m,r都没有赋值,也就是说 这玩意= ``` f[0][0]=0 ``` 那能不能找到**f[0][0]** 呢? **不能** Why? 因为你是这样写的(背包肯定要这么写 ``` for(int j = m; j >= rmb[i]; j--) for(int k = r; k >= rp[i]; k--) ``` 是倒着计算的 也就是说,**f[0][0]** 没有发现,答案就已经被计算 (除非开始就找到,但很难
by Raidrop @ 2021-06-02 18:55:20


@[阿尔托莉雅丶](/user/105820)
by Raidrop @ 2021-06-02 18:55:54


|