队伍配置_牛客博客

题目描述

萌学姐在玩大型手游《futa go》，他现在准备进入作战环节，所以他准备安排自己的队伍。
队伍配置里，可供玩家选择的作战人物被称作“从者”，玩家可以对每个“从者”可以装备至多1件的“概念礼装”，玩家具有一个cost上限值。详细定义如下：
1、每个从者和概念礼装都具有攻击值ATK。
2、每个从者和概念礼装都会占据一定的cost值。
3、每个从者和概念礼装只能上场一次，不能重复使用。
4、概念礼装只能装备在从者上，不能单独存在。
5、选择的从者和概念礼装的cost值之和不能超过玩家的cost上限值。
6、最多可以选择5名从者（在cost值限制下）。
现在给出玩家仓库的每个从者和每件概念礼装的ATK值和cost值，问在满足定义的条件下，队伍可以凑出的最大ATK值。

输入描述:

第1行输入三个整数n，m，d，代表玩家仓库的从者数量、概念礼装数量和cost上限值。
第2-n+1行，每行输入两个整数a1，b1，表示第i个从者的ATK值和cost值。
第n+2-n+m+1行，每行输入两个整数a2，b2，表示第i个概念礼装的ATK值和cost值。
数据保证：0<n,m≤300，25≤d≤138，1000≤a1≤15488，500≤a2≤2500，3≤b1,b2≤12

输出描述:

输出一行，一个整数，代表可以凑出的最大ATK值。

题解

首先我们可以明确一个问题，就是礼装的内部分配对于最后的结果是不影响的。即礼装装给谁都没有关系，所以这道题我们可以想象成选择最多5个从者和不超过从者的礼装来获得最大的ATK值。
其子问题其实跟01背包是一样的，就是一件物品我们选或者不选，我们设置状态为 $dp[i][j][k]$ 表示选择 $i$ 个从者和 $j$ 个礼装 $(j<=i)$ 花费上限为 $k$ 时获得的ATK最大值。
因为从者的个数对于礼装的个数有限制，我们可以先处理从者，即把所有的 $dp[i][0][k]$ 求出，再去考虑算礼装的情况。
在转移的时候注意一定是容量在个数前转移，写反会出现一个物品被选择多次的情况。

代码

#include<iostream>
#include<algorithm>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#include<stack>
using namespace std;
#define ll long long
#define ull unsigned long long
#define pb push_back
#define pii pair<int,int>
#define all(A) A.begin(), A.end()
#define fi first
#define se second
#define MP make_pair
#define rep(i,n) for(register int i=0;i<(n);++i)
#define repi(i,a,b) for(register int i=int(a);i<=(b);++i)
#define repr(i,b,a) for(register int i=int(b);i>=(a);--i)

template<typename T>
inline T read(){
    T s=0,f=1; char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-') f=-1;ch = getchar();}
    while(isdigit(ch)) {s=(s<<3)+(s<<1)+ch-48;ch = getchar();}
    return s*f;
}
#define gn() read<int>()
#define gl() read<ll>()
template<typename T>
inline void print(T x) {
    if(x<0) putchar('-'), x=-x;
    if(x>9) print(x/10);
    putchar(x%10+'0');
}

////////////////////////////////////////////////////////////////////////
int dp[305][305][150];
int tim[105],value[105];
////////////////////////////////////////////////////////////////////////
int main(){
    int n=gn(),m=gn(),d=gn();
    int ans=0;
    for(int i=1;i<=n;++i){
        int a=gn(),b=gn();
        for(int t=d;t>=b;--t){
            for(int k=1;k<=5;++k){
                dp[k][0][t]=max(dp[k][0][t],dp[k-1][0][t-b]+a);
                ans=max(dp[k][0][t],ans);
            }
        }
    }
    for(int i=1;i<=m;++i){
        int a=gn(),b=gn();
        for(int t=d;t>=b;--t){
            for(int k=1;k<=5;++k){
                for(int z=1;z<=k;++z){
                    dp[k][z][t]=max(dp[k][z][t],dp[k][z-1][t-b]+a);
                    ans=max(ans,dp[k][z][t]);
                }
            }   
        }
    }
    print(ans),putchar(10);
}

/**
* In every life we have some trouble
* When you worry you make it double
* Don't worry,be happy.
**/