一个类似背包的dp
时间$n^3$,空间$n^2$
不用读入优化会TLE
[code](https://www.luogu.com.cn/paste/8f5or0m0)
by Benzenesir @ 2022-09-24 23:50:42
@[Benzenesir](/user/258178) 大佬,想问一下,为什么特判完j<=fe[i]还要判f[k-cost[i]][j-fe[i]]>0啊qaq
by Ribaudiaux @ 2022-09-25 14:02:31
@[Ribaudiaux](/user/790282)
第二个就是用前面若干个花来组合,使这个组合加上当前的花能满足当前cost和fe的要求,f[k-cost[i]][j-fe[i]]>0其实就是看有没有一个这样的组合满足要求(虽然很意识流但多看几遍就大概明白了
by Benzenesir @ 2022-09-25 15:26:24
@[Benzenesir](/user/258178)
想通啦,感谢orzzzz
by Ribaudiaux @ 2022-09-25 19:31:31
@[Benzenesir](/user/258178)
```
if(j<=fe[i]){
//ts[j]=1;
f[k][j]=max(f[k-cost[i]][0]+be[i],f[k][j]);
}
```
大佬,为什么要有这句?,数据代进去发现非常重要,但不理解为啥
by kelanjie @ 2022-09-25 20:32:04
想通啦awa,打扰了
by kelanjie @ 2022-09-25 20:37:39
@[Benzenesir](/user/258178) 忘记谢谢了,感谢大佬,毕竟三条消息一起打扰了(*^▽^*)
by kelanjie @ 2022-09-25 20:39:42
写了个题解但没有通道,可以帮助加深理解
[这里](https://www.luogu.com.cn/blog/Benzne/p8548-ti-xie)
by Benzenesir @ 2022-09-25 22:02:56
@[Benzenesir](/user/258178) 谢谢orz
by End1essSummer @ 2022-09-26 21:47:21