传送门


题意:给\(s\)个玩家,\(n\)个城堡,\(m\)个士兵,每一个玩家向每一个城堡派出士兵数量已知,你要赢某个玩家的条件是你在这个城堡派出了大于这个玩家派出士兵数量的两倍,这个时候你在第\(i\)个城堡就会获得\(i\)分,你有\(m\)个士兵,问你最大分数是多少


解答:将每一个城堡看成一组,然后sort一遍了过后,那么你的花费大于第\(j\)个玩家的两倍的话,你在这一组里面的得分就是\((j+1)*(k+1)\)(\(j\)和\(k\)都是从0开始的)这样就可以使用分组背包求解,每一个物品的重量相当于\(a[k][j]*2+1\)

OI-Wiki分组背包


 

分类: DP

0 条评论

发表评论

邮箱地址不会被公开。 必填项已用*标注