洛谷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("\n");

//	}

	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;

}

巴特西

洛谷P1860 新魔法药水

最新文章

热门文章