洛谷5322 [BJOI2019]排兵布阵

题意

有 $N$ 座城堡和 $S$ 个玩家，每个玩家有 $M$ 个士兵。能占领城堡要求自己驻扎的兵力严格大于对方的两倍，玩家之间两两都会有独立的城堡争夺，占领第 $i$ 个城堡的收益是 $i$。

现在已知 $S$ 个玩家的驻军情况，求如何分配兵力，可以获得最大收益。

$S,N\le 100 \ \ \ \ M\le 20000$ 。

题解

很显然的背包问题，只是需要预处理一下重量。

用 $v[i][j]$ 表示第 $i$ 个城堡，占领前 $j$ 个玩家（按照兵力大小排序）的花费。可以用桶先记录最少能占领当前玩家的兵力，然后遍历所有兵力就可以得到 $v$ 。

方程式即为

$$f[k]=max(f[k],f[k-v[i][j]]+i\times j)$$

代码里的 n,m,s 对应题目里的 s,n,m 。

#include<bits/stdc++.h>

using namespace std;

inline int read()
{
    char ch=getchar(); int f=1,x=0;
    while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    return f*x;
}

int n,m,s,w[105][105],v[105][105],f[20005],buc[20005];

signed main()
{
    n=read(); m=read(); s=read();
    for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) w[i][j]=read();
    for (int j=1;j<=m;j++)
    {
        int cnt=0;
        for (int i=1;i<=n;i++) buc[w[i][j]<<1|1]++; //桶
        for (int i=1;i<=s;i++)
        {
            for (int k=1;k<=buc[i];k++) v[j][++cnt]=i; //注意中间的cnt个都需要被处理
            buc[i]=0; //顺便把桶清0
        }
        for (cnt++;cnt<=n;cnt++) v[j][cnt]=1e9; //剩下无论如何都不可能占领
    }
    for (int j=1;j<=m;j++)
    {
        for (int k=s;~k;k--)
        {
            for (int i=1;i<=n;i++)
            {
                if (k<v[j][i]) break;
                f[k]=max(f[k],f[k-v[j][i]]+j*i);
            }
        }
    }
    return !printf("%d",f[s]);
}