动态规划

题意：

分析：

这题和前面的Butterfly很相似，都是dp的组合。建议做完后去做做Butterfly

那么现在开始分析这题吧：
假设我们选了i个savent，花费了d1的cost值，那么现在我们只有d-d1的cost值，
我们用d-d1的cost值，到所有的概念礼装中去选最多i个概念礼装。
在这个过程中我们要尽量使savent的atk和最大，也要尽量使概念礼装的atk和最大

也就是说我们要知道:
花费d1选i个savent的最大atk
花费d2最多选i个概念礼装的最大atk （d1+d2 = d）
这便是我们真正的问题，这两个问题是相似的。

对于第一个问题，我们开一个动态规划数组
dp1[i][j][k]:在前i个中选j个savent，最多消耗k所获得的最大atk
很容易就能发现其状态转移方程：
dp1[i][j][k] = max(dp1[i-1][j][k],dp1[i-1][j-1][k-s[i].cost] + s[i].atk)
在这个转移公式中要保证j<=i,且k>=前i个cost最小的savent的cost和(我们可以排序后用前缀和sum)

而对于第二个问题状态的定义和转移同样也是类似的：
dp2[i][j][k]:在前i个中至多选j个概念礼装，最多消耗k所获得的最大atk
状态转移方程：
dp2[i][j][k] = max(dp2[i-1][j][k],dp2[i-1][j-1][k-c[i].cost] + c[i].atk)
在这个转移方程中要保证k-c[i].cost>=0
否则dp2[i][j][k] = dp2[i-1][j][k]
和上衣个转移方程略有不同关键在于至多二字

最后的答案
ans = max(dp1[n][j][k]+dp2[m][j][d-k] 0<=j<=min(n,5))

代码如下：

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
struct savent { int atk, cost; bool operator<(const savent& s1) { return cost < s1.cost; } } savents[310];
struct cd { int atk, cost; bool operator<(const cd& c1) { return cost < c1.cost; } } cds[310];
int n, m, d;
ll dp1[310][10][200];
ll dp2[310][10][200];
ll sum[310];

int main() {
    ios::sync_with_stdio(0);
    cin >> n >> m >> d;

    for (int i = 1;i <= n;i++)cin >> savents[i].atk >> savents[i].cost;
    sort(savents + 1, savents + 1 + n);for (int i = 1;i <= n;i++)sum[i] = sum[i - 1] + savents[i].cost;
    for (int i = 1;i <= m;i++)cin >> cds[i].atk >> cds[i].cost;

    for (int i = 1;i <= n;i++)
        for (int j = 1;j <= min(5,i);j++)
            for (int k = sum[j];k <= d;k++)
                dp1[i][j][k] = max(dp1[i - 1][j][k], dp1[i - 1][j - 1][k - savents[i].cost] + savents[i].atk);

    for (int i = 1;i <= m;i++) {
        for (int j = 1;j <= min(5,m);j++) {
            for (int k = 1;k <= d;k++) {
                if (j > i)dp2[i][j][k] = dp2[i][i][k];
                else if (k - cds[i].cost < 0)dp2[i][j][k] = dp2[i - 1][j][k];
                else dp2[i][j][k] = max(dp2[i - 1][j][k], dp2[i - 1][j - 1][k - cds[i].cost] + cds[i].atk);
            }
        }
    }
    ll ans = 0;
    for (int i = 0;i <= min(n,5);i++)
        for (int j = sum[i];j <= d;j++)
            ans = max(ans, dp1[n][i][j] + dp2[m][i][d - j]);
    cout << ans << endl;
}

一开始没有注意到从者最多5个，疯狂报错。。。。。。😂