题目大意
具体题面及输入格式戳我！
商店里有\(N\)种药水，每种药水都有一个售价和回收价。
小\(S\) 攒了\(V\)元钱，还会\(M\)种魔法，可以把一些药水合成另一种药水。
他在第一天可以购买药水、使用最多\(K\)次魔法，然后第二天在把手头上的药水出售。
现在小\(S\)希望知道两天之内他最多能够赚多少钱？
数据范围：\(N\leq 60\) ; \(M\leq 240\) ; \(V\leq 10^3\) ; \(K\leq30\) ;
思路与解法
这么好的题目Luogu上竟然没人做，非常全面的一道\(DP\)题。
注意到物品的合成是可以嵌套进行的(用合成的东西去合成新的东西)。
这个就非常的恶心。
\(Solve_a\)
我们假设现在合成只能有一层，即不能用合并出来的东西去合并新的东西。
那么这就是一道非常简单的二维背包了。 所以我们考虑如何消除嵌套合并的影响。
设\(f[i][j]\)表示使用\(j\)次魔法得到物品\(i\)的最低费用。显然初始\(f[i][0] = price[i]\)
那么发现无法直接转移\(f\)，但是对于每一个魔法我们是可以\(DP\)的：
我们枚举一个魔法，设\(r[i][j]\)表示得到这个魔法的前i个原料，使用了j次魔法的最低价格.
那么转移：
\[r[\ i\ ][\ j_1+j_2\ ] = r[i-1][j_1] + f[\ itm[i]\ ][j_2]\]
其中\(itm[i]\)为这个魔法的第\(i\)个原料，\(f\)的含义见上。
转移完后用\(r[i][j]\)更新\(f[i][j+1]\)(把这些原料合成又需要一次魔法)即可。
发现一个问题，\(f\)是我们正在求的东西，但是转移中又出现了\(f\)。
一个最直接的想法就是\(TopSort\)一遍再\(DP\)，但是此题数据非常恶心每组数据的合成关系都出现了环。
发现我们最多只需要做\(N\)次，所有的\(f\)就都到位了，所以就做\(N\)遍这个\(DP\)即可。
这个部分的时间复杂度为\(O(NMK^2)\)，难点在于想到使用\(r\)数组。
\(Solve_b\)
求出了\(f\)数组，剩下的部分就是一个很简单的二维背包了。
\(g[i][j][k]\)表示前\(i\)个物品，使用了\(j\)元，用了\(k\)次魔法的最大利润。
把每一个\(f[i][r]\)看成一个物体，枚举使用次数\(e\)即可：
\[g[i][j][k] = max(\ g[i-1][\ j-e*f[i][r]\ ][\ k-e*r\ ] + profit(i)*e\ )\]
直接这样转移复杂度过高，使用完全背包问题的状态优化，把状态优化为二维\(g[j][k]\)即可，注意枚举顺序。
这个部分时间复杂度为\(O(NK^2V)\)，总时间复杂度为\(O(\ NK^2(M+V)\ )\)。
实现代码：
#include<bits/stdc++.h>
#define RG register
#define IL inline
#define pb push_back
#define ll long long
#define gi(x) scanf("%lld",&x);
#define fp(i,j,k) for(RG ll i = j; i <= k; i ++)
#define INF 1e9+7
using namespace std;
ll f[65][35] , r[65][35] , g[1005][35] ;
ll N , M , V , K , pft[65] , cnt;
ll itm[250][605] , sum[250] , Ans; vector<ll>gp[ 65 ];
IL void Min(RG ll &x,RG ll y){if(x > y)x = y;}
IL void Max(RG ll &x,RG ll y){if(x < y)x = y;}
const ll zr = 0;
IL void DP1(RG int u){
RG ll szz = gp[u].size();
for(RG ll sq = 0; sq < szz; sq ++){
RG ll id = gp[u][sq];
fp(i,0,sum[id])fp(j,0,K)r[i][j] = INF;
r[0][0] = 0;
for(RG ll i = 1; i <= sum[id]; i ++)
for(RG ll j1 = 0; j1 <= K; j1 ++)
for(RG ll j2 = 0; j2 + j1 <= K; j2 ++){
Min( r[i][j1+j2] , r[i-1][j1] + f[ itm[id][i] ][j2] );
}
for(RG ll j = 0; j <= K-1; j ++)
Min(f[u][j+1] , r[sum[id]][j]);
}return;
//f[u][j]: 表示使用j次魔法，得到u物品的最小花费
//r[i][j]: 表示得到此魔法前的前i个原料，使用了j次魔法的最小花费。
}
IL void DP2(){
for(RG ll i = 1; i <= N; i ++)
for(RG ll e = 0; e <= K; e ++) //枚举物品
for(RG ll k = e; k <= K; k ++) //用了多少次魔法
for(RG ll val = f[i][e]; val <= V; val ++) //预估花费
Max(g[val][k],g[val-f[i][e]][k-e] + pft[i] ) , Max(Ans , g[val][k]-val);
// g[i][j][k] 表示前i个物品，花费了j元 ，使用了k次魔法 的最大利润。
return;
}
int main(){
gi(N); gi(M); gi(V); gi(K);
fp(i,0,N)fp(j,0,K)f[i][j] = INF;
for(RG ll i = 1; i <= N; i ++){ gi(f[i][0]); gi(pft[i]);}
for(RG ll i = 1; i <= M; i ++){
RG ll x,y; gi(x); gi(y);
sum[i] = y;
for(RG ll j = 1; j <= y; j ++)gi(itm[i][j]);
gp[x].pb(i);
}
for(RG int i = 1; i <= N; i ++)
for(RG int e = 1; e <= N ; e ++)
DP1(e);
Ans = -INF;
DP2(); cout << max(Ans , zr); return 0;
}