自动搬运

查看原文

来自洛谷，原作者为

	Santiego 平泽唯天下第一

搬运于2025-08-24 22:09:32，当前版本为作者最后更新于2019-07-14 16:29:22，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

$\text{My Blog}$

比较好想的DP，设$dp[i][j]$表示第$i$个城堡时，已派出$j$个士兵。决策时，贪心派出恰好严格大于某一玩家派出的数量的两倍（不然浪费）。我们发现又可以排序预处理出$a[i][j]$表示第$i$个城堡，出兵数量第$j$大的人出兵数量（因为这样可以很容易算出贡献，即为$k\times i$）

dp转移方程即为： $dp[j]=MAX(dp[j-a[i][k]*2-1]+k*i, dp[j]);$

AC Code:

#include <cstdio>
#include <algorithm>
#define MAX(A,B) ((A)>(B)?(A):(B))
using namespace std;
int s,n,m,dp[20002],a[110][110],ans;
signed 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]);
    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;j>=0;--j) //倒序枚举已派出兵
            for(int k=1;k<=s;++k) //对s个玩家决策
                if(j>a[i][k]*2)
                    dp[j]=MAX(dp[j-a[i][k]*2-1]+k*i, dp[j]);
    for(int i=0;i<=m;++i) ans=MAX(ans, dp[i]);
    printf("%d\n", ans);
    return 0;
}
/*
 dp[i][j]第i个城堡时，已派出j个士兵
 a[i][j]第i个城堡，第j个人出的兵
 */