首页 > 代码库 > [bzoj1296][SCOI2009]粉刷匠(泛化背包)

[bzoj1296][SCOI2009]粉刷匠(泛化背包)

http://www.lydsy.com:808/JudgeOnline/problem.php?id=1296

分析:

首先预处理出每一行的g[0..T]表示这一行刷0..T次,最多得到的正确格子数。这个做法只要把每一行连续的个数分别求出来,然后从大到小累加就行

然后整体来看,就是对n个物品做泛化背包了。

[bzoj1296][SCOI2009]粉刷匠(泛化背包)