题目链接：

[BJOI2019]排兵布阵

对于每座堡垒，将$s$个对手排序，显然如果安排的兵力能打败第$i$个对手就一定能打败前$i-1$个。

那么对于第$i$座城堡，可以看做有$s+1$个物品(可以不安排兵力)，第$j$个物品代价为$2*v[j]+1$，收益为$i*j$。

剩下的只需要将每座城堡的所有物品放在一组然后分组背包即可。

#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<vector>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int f[120][20010];
int cnt[120];
int g[120][120];
int h[120][120];
int s[120];
int mp[120][120];
int n,m,k;
int main()
{
scanf("%d%d%d",&k,&n,&m);
for(int i=1;i<=k;i++)
{
for(int j=1;j<=n;j++)
{
scanf("%d",&mp[i][j]);
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=k;j++)
{
s[j]=mp[j][i];
}
sort(s+1,s+1+k);
for(int j=1;j<=k;j++)
{
if(2*s[j]+1<=m)
{
g[i][++cnt[i]]=2*s[j]+1;
h[i][cnt[i]]=i*j;
}
}
}
for(int i=1;i<=n;i++)
{
for(int j=0;j<=m;j++)
{
for(int k=0;k<=cnt[i];k++)
{
if(j>=g[i][k])
{
f[i][j]=max(f[i][j],f[i-1][j-g[i][k]]+h[i][k]);
}
}
}
}
printf("%d",f[n][m]);
}