队伍配置

题意

有个从者，个装备，最多选择个从者，每个从者只能装备一个装备，可以不装，从者和装备都会消耗获得相应的，问不超过的可以获得的最大是多少？

分析

显然装备装在任何人身上都是等价的，所以我们可以先考虑从者，再考虑装备。

定义为选了个从者，件装备，消耗体积所获得的最大。

我们可以先不考虑装备，处理出所有的情况。

然后我们再枚举装备数量。

#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pii pair<int,int>
#define int long long
const int inf = 0x3f3f3f3f;
const int maxn = 310;
const int M = 1e9+7;
int n,m,d;

struct node
{
    int x,y;
}a[maxn],b[maxn];

int dp[6][6][150];

signed main()
{
    cin>>n>>m>>d;
    for(int i = 1; i <= n; i++) 
    {
        cin>>a[i].x>>a[i].y;
    }
    for(int i = 1; i <= m; i++) 
    {
        cin>>b[i].x>>b[i].y;
    }
    for(int i = 1; i <= n; i++) 
    {
        for(int j = d; j >= a[i].y; j--)
        {
            for(int k = 5;k >= 1; k--)
            {
                dp[k][0][j] = max(dp[k][0][j],dp[k-1][0][j-a[i].y]+a[i].x);
            }
        }
    }
    for(int i = 1; i <= m; i++)
    {
        for(int j = d; j >= b[i].y; j--)        //枚举体积
        {
            for(int k = 5; k >= 1; k--)        //枚举从者数量
            {
                for(int l = k; l >= 1; l--)        //枚举装备数量
                {
                    dp[k][l][j] = max(dp[k][l][j],dp[k][l-1][j-b[i].y]+b[i].x);
                }
            }
        }
    }
    int ans = 0;
    for(int i = 1; i <= 5; i++) 
    {
        for(int j = 0; j <= i; j++) 
        {
            for(int k = 0; k <= d; k++)
            {
                ans = max(ans,dp[i][j][k]);
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}