发表文章

[最新] 2018牛客暑假多校三 A(01背包)

weixin39453270 4月前 2

题目描述:

    有n个队伍,每个队伍都会有pi个物理专家,ai个算法专家,ci个代码专家,mi个数学专家,而每支队伍都会有一个值gi,gi越大队伍赢面越大。每当邀请第i支队伍,则就需要将队伍内的所有人都邀请过来,否则全都不来。问在限制最多只能有P个物理,A个算法,C个代码,M个数学的前提下,最多邀请多少个队伍,使得他们带来的g的总和最大。

题目分析:

    因为问题是在某种容量限制的情况下求出最大的总和,因此毫无疑问就是一个带有四重限制的01背包的问题。

    而同时因为题目要求我们统计的是要取哪些队伍,因此我们可以通过状态压缩,若第i支队伍可取,就在第i位置1,最后统计哪一位为1即可。

代码:

#include<bits/stdc++.h>
#define maxn 40
using namespace std;
int P[maxn],A[maxn],C[maxn],M[maxn],g[maxn];
int p,a,c,m;
int f[maxn][maxn][maxn][maxn];
long long dp[maxn][maxn][maxn][maxn];
int bit(long long tt){
    int ret=0;
    while(tt){
        if(tt&1)ret++;
        tt>>=1;
    }
    return ret;
}
int main()
{
    int n;

    cin>>n;
    for(int i=1;i<=n;i++)
        scanf("%d%d%d%d%d",&P[i],&A[i],&C[i],&M[i],&g[i]);
    scanf("%d%d%d%d",&p,&a,&c,&m);
    for(int i=1;i<=n;i++){//经典的01背包做法
        for(int j=p;j>=P[i];j--){
            for(int k=a;k>=A[i];k--){
                for(int l=c;l>=C[i];l--){
                    for(int o=m;o>=M[i];o--){
                        if(f[j-P[i]][k-A[i]][l-C[i]][o-M[i]]+g[i]>f[j][k][l][o]){
                            dp[j][k][l][o]=dp[j-P[i]][k-A[i]][l-C[i]][o-M[i]]|(1LL<<i);//状态压缩
                            f[j][k][l][o]=f[j-P[i]][k-A[i]][l-C[i]][o-M[i]]+g[i];
                        }
                    }
                }
            }
        }
    }
    int tmp=bit(dp[p][a][c][m]);
    cout<<tmp<<endl;
    if(!tmp) return 0;
    int cnt=0;
    for(int i=1;i<=n;i++){
        if(dp[p][a][c][m]&(1LL<<i)){
            if(cnt==tmp-1) {
                tmp=i-1;
                break;
            }
            cout<<i-1<<" ";
            cnt++;
        }
    }
    cout<<tmp<<endl;
    return 0;
}

 

相关推荐
最新评论 (0)
返回
发表文章
weixin39453270
文章数
104
评论数
0
注册排名
761180