洛谷P1860 新魔法药水
动态规划：
这个题目调了我好久。。。。结果循环变量写错了。。。
而且题目有个坑！！！只能用开始给你的$v$元买入东西
回归正题：
我们定义状态$ans[i][j]$表示第$i$个物品用了至多$j$次魔法的最小花费，但是我们发现这样子的话不好与合成关系联系在一起，那么我们再定义一个数组$f[i][j]$表示某一个合成关系中，前$i$个物品中用至多$j$次魔法合成的最小花费
那么最后就普通$dp$就行了
#include<iostream>
#include<cstdio>
#include<cstring>
#define inf 0x7f7f7f7f
#define M 300
#define K 31
using namespace std;
struct Magic
{
int to,num,thing[M];
}magic[M];
int n,m,v,k;
int pay[M],get[M],f[M][M],ans[M][M],dp[M][1007];
int main()
{
scanf("%d%d%d%d",&n,&m,&v,&k);
for(int i=1;i<=n;++i)
scanf("%d%d",&pay[i],&get[i]);
for(int i=1;i<=m;++i)
{
scanf("%d%d",&magic[i].to,&magic[i].num);
for(int j=1;j<=magic[i].num;++j)
scanf("%d",&magic[i].thing[j]);
}
for(int i=1;i<=n;++i)
for(int j=0;j<=k;++j)
ans[i][j]=pay[i];
for(int l=1;l<=k;++l)
{
for(int i=1;i<=m;++i)
{
for(int j=1;j<=magic[i].num;++j)
for(int o=0;o<l;++o)
{
f[j][o]=inf;
for(int oo=0;oo<=o;++oo)
f[j][o]=min(f[j][o],f[j-1][o-oo]+ans[magic[i].thing[j]][oo]);
}
ans[magic[i].to][l]=min(ans[magic[i].to][l],f[magic[i].num][l-1]);
}
}
// for(int i=1;i<=n;++i)
// {
// for(int j=1;j<=m;++j)
// printf("%d ",ans[i][j]);
// printf("
");
// }
for(int i=1;i<=n;++i)
for(int j=0;j<=k;++j)
for(int o=0;o<=k-j;++o)
for(int l=ans[i][j];l<=v;++l)
dp[j+o][l]=max(dp[j+o][l],dp[o][l-ans[i][j]]+get[i]-ans[i][j]);
printf("%d",dp[k][v]);
return 0;
}