。fij表示选到前 i 座城堡已经用了j个士兵所能获得总分的最大值。倘若直接枚举每座城堡派几个士兵效率是 O(nm^2)，但是我们发现只有多获胜一个人才能使总分增多，所以我们可以考虑枚举每座城堡赢几个人，效率变成O(nms)。
代码：
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=110,M=20010;
int a[N][N];
int s,n,m,f[M];
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]);
a[j][i]=a[j][i]*2+1;
}
for(int i=1; i<=n; i++)
sort(a[i]+1,a[i]+1+s);
for(int i=1; i<=n; i++)
for(int j=m-1; j>=0; j--)
for(int k=1; k<=s; k++) {
if(a[i][k]+j>m)
break;
f[a[i][k]+j]=max(f[a[i][k]+j],f[j]+k*i);
}
int ans=0;
for(int i=1; i<=m; i++)
ans=max(ans,f[i]);
printf("%d\n",ans);
return 0;
}
原文：https://www.cnblogs.com/mysh/p/11456531.html