luogu P5322 [BJOI2019] 排兵布阵

· · 题解

原题链接

#include<bits/stdc++.h>
using namespace std;
/*
样例分析：
1 2 10
2 2 6

5 5 0 

解题思路：
注意到关键词“这 s 场对决的派遣士兵方案必须相同” 

分组背包： 
组别：第 i 座城堡 
物品：第 j 个敌人对第 i 座城堡 
价值：i
体积：敌人士兵数目二倍加一

然而以上分法还有问题，即，对于样例二来讲，在上述分法的
定义下，第二座城堡只得 2 分，然而实际上得 4 分，所以，
还需要将每个组别经行排序，并使其价值为 j*i，即解决问题 
*/
const int M = 20010,N=110;
int s,n,m; 
int v[N][N];//v[i][j 第 i 座城堡第 j 个敌人的战胜代价 
int f[M]; 

int main(){
    scanf("%d%d%d",&s,&n,&m);
    for(int j=1;j<=s;j++)
        for(int i=1;i<=n;i++)
            scanf("%d",&v[i][j]),v[i][j]=v[i][j]*2+1;

    for(int i=1;i<=n;i++)
        sort(v[i]+1,v[i]+s+1); 

    for(int i=1;i<=n;i++){//100 
        for(int j=m;j>=0;j--){
            for(int z=1;z<=s;z++)
                if(j>=v[i][z])
                    f[j]=max(f[j],f[j-v[i][z]]+i*z);
        }
    }

    printf("%d",f[m]);
    return 0;
}