队伍配置

题意:给定n个从者,m个概念礼装,然后每个从者,概念礼装都有一定的ATK值和所需要的cost值,然后现在玩家的cost值上线为d,并且选择的从者数大于等于概念礼装数,从者数要小于5个
题解:01背包加强版
建立 数组,表示消耗cost值为i,获得j个从者,和k个概念礼装得到的ATK值
因为输入的时候先输入从者的数据,所以先计算dp[i][k][0]
所以对于计算从者的时候有:
现在有一个增加x的ATK值,以及消耗y的cost值得从者
消耗cost的j值获得k个从者与消耗j-y的cost值获得k-1个从者加上当前的从者的ATK值比较大小
同理,接下来计算能有多少的概念礼装:
然后再对于每一种情况进行比较,取最大值
时间复杂度:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int f[200][10][10];
int ans=0;
int main()
{
    int n,m,d;
    cin>>n>>m>>d;
    for (int i=0; i<n; i++)
    {
        int x,y;
        cin>>x>>y;
        for (int j=d; j>=y; j--)
        {
            for (int k=1; k<=5; k++)
            {
                f[j][k][0]=max(f[j][k][0],f[j-y][k-1][0]+x);
                ans=max(ans,f[j][k][0]);
            }
        }
    }
    for (int i=0; i<m; i++)
    {
        int x,y;
        cin>>x>>y;
        for (int j=d; j>=y; j--)
        {
            for (int k=1; k<=5; k++)
            {
                for (int p=1; p<=k; p++)
                {
                    f[j][k][p]=max(f[j][k][p],f[j-y][k][p-1]+x);
                    ans=max(ans,f[j][k][p]);
                }
            }
        }
    }
    cout<<ans<<endl;
}