分析：
1、用 vector<int> v[i] 来存 i 城堡， s 个对手所安排的士兵数量。
2、设 dp[i][j] 表示 i 城堡前，在当前最大派兵量为 j 时所能获得的最大价值。
3、不难想到的是，遍历 s 个对手，再用两个 for 遍历一下该城堡中各个对手的派兵量。然后对于能派的就派去看看能否更新 dp 值。
4、再者我们考虑贪心思想：若第 i 个城堡中， A 选手派出 a 个兵，那至少需要派 2 * a + 1个兵才能对答案有贡献；再者若 B 选手派出 b 个兵，且 b > a ，那么如果能派出 2 * b + 1 个兵的话，则对于 A 选手那边也可以做出贡献。故我们需要使 v[i] 进行排序，这样 dp 时如果后面大的能满足，那么直接使得 （当前以上的选手数量） * i ，得出当前城堡的贡献即可。
此算法的时间复杂度为 O（nms），看上去达到 2 * 10 ，但在 dp 中会有 break 来剪枝 。
此外由于转移方程中只与上一层即 dp[i - 1][] 有关，故可降到一维。
代码如下：
#define IO freopen("test.in","r",stdin),freopen("test.out","w",stdout) #define inf 0x3f3f3f3f #define lson root<<1 #define rson root<<1|1 #include <set> #include <map> #include <deque> #include <queue> #include <stack> #include <cmath> #include <ctime> #include <bitset> #include <cstdio> #include <string> #include <vector> #include <cstdlib> #include <cstring> #include <cassert> #include <iostream> #include <algorithm> #include <unordered_map> using namespace std; int s,n,m; int a[108],dp[20008]; vector<int> v[108]; int main() { //IO; scanf("%d%d%d",&s,&n,&m); for(int i=1;i<=n;i++) a[i]=inf; int A; for(int i=1;i<=s;i++){ for(int j=1;j<=n;j++){ scanf("%d",&A); v[j].push_back(A); a[j]=min(a[j],A); } } for(int i=1;i<=n;i++) sort(v[i].begin(),v[i].end()); for(int i=1;i<=n;i++){ for(int j=m;j>a[i]*2;j--){ for(int k=0;k<v[i].size();k++){ if(j<=v[i][k]*2) break; dp[j]=max(dp[j],dp[j-(v[i][k]*2+1)]+(k+1)*i); } } } printf("%d\n",dp[m] ); }