蒟蒻提问,为什么动态转移方程不是这样?
查看原帖
蒟蒻提问,为什么动态转移方程不是这样?
463562
Dreamerlee✅楼主2021/3/19 09:41

蒟蒻想法:

for(int i=1; i<=n; i++)
       for(int j=0; j<=m; j++)
           for(int k=0; k<=min(j, a[i]); k++)
              f[i][j] = (f[i-1][j] + f[i-1][j-k])%mod;
//这里f[i-1][j]表示不选这个i品种的花,前面i-1品种的花凑够j盆的最佳方案数,f[i-1][j-k]表示选i品种的花k盆,加上前面i-1品种的花凑够剩下的j-k盆的最佳方案数,然后两个方案数加起来

而现实的残酷却是这样的动态方程:

for(int i=1; i<=n; i++)
       for(int j=0; j<=m; j++)
           for(int k=0; k<=min(j, a[i]); k++)
              f[i][j] = (f[i][j] + f[i-1][j-k])%mod;
```cpp
2021/3/19 09:41
加载中...