题目：https://loj.ac/problem/3092
同一个人的不同城堡之间没有什么联系，只是和<=m。所以对每个城堡的 s 个值排序，做一个 f[ i ][ j ] 表示第 i 个城堡花 j 的代价最大能得到多少收益。
dp[ i ][ j ] 表示前 i 个城堡花 j 的代价的最大收益。 dp[ i ][ j ] = max( dp[ i-1 ][ k ] + f[ i ][ j-k ] ) 。
发现 f[ i ][ * ] 是一个分 s 段的函数。所以枚举 s 段即可。也就是把 f 改成 f[ i ][ s ] 表示第 i 个城堡得到 s 的收益最少花多少代价。
dp[ i ][ j ] = max( s + dp[ i-1 ][ j-f[ i ][ s ] ] ) 。注意代价要乘 i 。
时间是 2e8 却能过。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int rdn()
{
int ret=;bool fx=;char ch=getchar();
while(ch>''||ch<''){if(ch=='-')fx=;ch=getchar();}
while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();
return fx?ret:-ret;
}
int Mx(int a,int b){return a>b?a:b;}
const int N=,M=2e4+;
int cnt,n,m,a[N][N],f[N][N],dp[N][M];
int main()
{
cnt=rdn();n=rdn();m=rdn();
for(int i=;i<=cnt;i++)
for(int j=;j<=n;j++)a[j][i]=rdn();
for(int i=;i<=n;i++)
{
sort(a[i]+,a[i]+cnt+);
for(int j=;j<=cnt;j++)
f[i][j]=*a[i][j]+;
}
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
for(int s=;s<=cnt;s++)
{
if(j<f[i][s])break;
dp[i][j]=Mx(dp[i][j],s*i+dp[i-][j-f[i][s]]);
}
printf("%d\n",dp[n][m]);
return ;
}