思路
这题可以用 DP 做。题目中一共存在 3 个参数 \(s,n,m\)，我们要求的是在 \(n\) 个城堡中总共派遣 \(m\) 名士兵的最大得分。由此我们可以得出，DP 状态的定义与 \(n,m\) 有关。
所以我们设计 DP 状态：\(dp[i][j]\) 表示前 \(i\) 个城堡中，总共派遣 \(j\) 名士兵的最大得分。
不难想出最简单、暴力的转移方法：枚举第 \(i\) 个城堡派遣的士兵数 \(k\in\left\{0,j\right\}\)，然后一一比较当前 \(dp[i][j]\) 和 \(dp[i-1][j-k]+Score(i,k)\cdot i\) 求最大值（\(Score(i,k)\) 表示在第 \(i\) 个城堡派遣 \(k\) 名士兵可以在与 \(s\) 个人的游戏中占领城堡 \(i\) 的次数，可以通过枚举 \(l\in\left\{1,s\right\}\) 比较来求出）。
我们分析这个方法的时间复杂度：枚举 \(i,j\) 的时间复杂度分别为 \(\mathcal O(n)\) 和 \(\mathcal O(m)\)，枚举 \(k,l\) 的时间复杂度分别为 \(\mathcal O(m)\) 和 \(\mathcal O(s)\)，所以总时间复杂度就是 \(\mathcal O(nm^2s)\)，显然不能通过全部数据。转移方式需要进行优化。
观察题目，我们发现，在第 \(i\) 个城堡派遣的士兵数，在贪心思想下，一定是某个人 \(p\in\left\{1,s\right\}\) 的 \(2\cdot a[p][i]+1\)（\(a[p][i]\) 即题目给定的第 \(p\) 个人在城堡 \(i\) 所派遣的士兵数），因为，如果我们多派遣一个或少派遣一个，都会导致白白浪费一名士兵或少得到 \(i\) 分。据此，我们有新的转移方法：用 \(a[i][j]\) 存储第 \(i\) 个城堡中，第 \(j\) 个人派遣的士兵数（（注意：这个 \(j\) 不等同于人的编号，仅是一个存储的下标，不要将这二者搞混了），我们每一个 \(a[i]\) 代表的数组进行升序排序后，在转移的循环内枚举 \(k\in\left\{1,s\right\}\)，若 \(2\cdot a[k][i]+1\ge j\)，代表我们即使将所有的 \(j\) 个士兵都派遣到城堡 \(i\)，也无法占领这座城堡，干脆就不派遣任何士兵，而往后的 \(a[k][i]\) 都比当前的 \(a[k][i]\) 大，所以直接 break；否则，我们可以试着在城堡 \(i\) 派遣 \(2\cdot a[k][i]+1\) 名士兵，这样我们就可以以最少的兵力占领第 \(i\) 个城堡，由于 \(1\sim k\) 这 \(k\) 个人的 \(a[k][i]\) 都比当前的 \(a[k][i]\) 小，所以我们同样可以占领这 \(k\) 个人的城堡，总的得分就是 \(i\cdot k\)。
所以，我们有状态转移方程：
由于我们可能不会在城堡 \(i\) 上派遣兵力，所以 \(dp[i][j]\) 可以初始化为 \(dp[i-1][j]\)。最终的答案依据定义，就是 \(dp[n][m]\)，直接输出即可。
这个转移方式的时间复杂度是 \(\mathcal O(nms)\)，可以通过本题。
示例代码
#include<bits/stdc++.h>using namespace std;typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;const int INF=0x3f;
const double EPS=1e-8;
const int N=105;
const int M=2e4+5;int s,n,m,dp[N][M];
pii a[N][N];template<typename T=int>
T rd(){char ch=getchar();T x=0,f=1;while(!isdigit(ch)){if(ch=='-') f*=-1;ch=getchar();}while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}return x*f;
}int main(){cin.tie(nullptr)->sync_with_stdio(false);cin>>s>>n>>m;for(int i=1;i<=s;i++)for(int j=1;j<=n;j++)cin>>a[j][i].first,a[j][i].second=j;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=0;j<=m;j++){dp[i][j]=dp[i-1][j];for(int k=1;k<=s;k++){if(a[i][k].first*2>=j)break;dp[i][j]=max(dp[i][j],dp[i-1][j-2*a[i][k].first-1]+k*i);}}}cout<<dp[n][m]<<endl;return 0;
}