Description
共有\(n\)种物品，每种物品都有\(t\)个，每种物品的重量是\(a_i\times 2+1\),价值为\(i\),现在你有一个重量为\(m\)的背包，请问你的价值最大是多少？
Solution
把题面翻译成这样，可以看出是一道分组背包问题。
显然若想占领一座城堡，这座城堡已经派了\(a\)人，则至少需要派\(a\times 2 +1\)人才能占领，因为题目中说严格大于，若多派人显然是无效的，浪费的。故可以把\(a \times 2+1\)作为城堡的“重量”
和分组背包不同的是，分组背包一组只需要选一个，而本题一组里可以攻打很多人，获得很多份价值。
那么如何处理呢？
不难发现若第一个人往一座城堡派\(i\)人，第二个人往同一座城堡里派\(j\)人，且\(i>j\)，若打下了\(i\)，则一定打下了\(j\)
因此，我们可以对每座城堡的每个人派兵力从小到大排序，显然若打下了\(i\)城堡则\(i\)以前的城堡一定都打下了，故取贡献的时候也要乘上已经枚举过的人数量。
由于输入的时候是按照第\(i\)个人攻打第\(j,j+1,j+2...n\)座城堡输入的，排序的时候需要反转一下，用sort就好。
还是一道非常巧妙的分组背包呢
Code
#include <iostream>
#include <cstdio>
#include <algorithm>
#define N 1010
#define M 200000
using namespace std;
int s,n,m;
int a[N][N];
int f[M];
int index = 0;
int maxn = -1;
int main()
{
scanf("%d%d%d",&s,&n,&m);
for(int i=1;i<=s;i++)
{
for(int j=1;j<=n;j++)
{
scanf("%d",&a[j][i]); //为处理方便，第一维存城堡
}
}
for(int i=1;i<=s;i++) sort(a[i]+1,a[i]+s+1); //反转排序
for(int i=1;i<=n;i++) //由于我们把每一种城堡看作一组，所以先枚举
{
for(int j=m;j>=0;j--) //倒着扫一遍重量
{
for(int k=1;k<=s;k++) //每一个人，即每一件物品
{
if(j >= 2*a[i][k]+1) //如果能打
{
f[j] = max(f[j],f[j-2*a[i][k]-1] + k*i); //处理价值的时候记得乘上k，因为排好序后前面的人一定能打
}
}
}
}
cout<<f[m]<<endl;
return 0;
}