P5322 [BJOI2019]排兵布阵(背包)

· · 题解

题意:https://www.luogu.org/problem/P5322

初次拿到没有思路,看了眼题解马上明白了

将城堡看成为物品,派出的兵力为代价,获胜的场数*第几个城堡为价值,这就是背包的模型

f[j]表示已经派出j的兵力的最大价值

枚举城堡i,将每个人派出的兵力排序后,记第k个人派出的兵力为a[i][k],由于已经排好序,能打败第k个敌人就能打败第k-1个,因此枚举敌人k,贪心地派出刚好比他的兵力两倍多1的兵力转移

f[j]=max(f[j],f[j-(2*a[i][k]+1)]+i*k)

code:

#include<bits/stdc++.h>
using namespace std;
const int maxs=110;
const int maxn=110;
const int maxm=20010;
int S,n,m,ans;
int a[maxs][maxn],f[maxm];
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]);
    for(int i=1;i<=n;i++)sort(a[i]+1,a[i]+S+1);
    for(int i=1;i<=n;i++)
        for(int j=m;j>=0;j--)
            for(int k=1;k<=S;k++)
                if(j>=2*a[i][k]+1)f[j]=max(f[j],f[j-(2*a[i][k]+1)]+i*k);
    printf("%d",f[m]);
    return 0;
}