神奇的DP

大概是用DP预处理要预处理的内容

然后用DP预处理

最后DP背包跑答案

 

卡了我很久有必要详细讲一下

题目描述

商店里有N种药水,每种药水都有一个售价和回收价。小S攒了V元钱,还会M种魔法,可以把一些药水合成另一种药水。他一天可以使用K次魔法,问他一天最多赚多少钱?

输入输出格式

输入格式:

第一行四个数N、M、V、K

接下来N行,每行两个数,表示药水的售价和回收价。

接下来M行,每行若干个数,第一个数表示魔法的成品,第二个数是原料的种数,接下来为各种原料的编号

输出格式:

一个数,表示小S的最大利润

·

N<=60 M<=240

V<=1000

k<=30

我们先考虑这是个背包

然后很自然的只需要求每个物品的min 购买价,然后二位费用xjb转移就可以得出答案

DP求这个部分.

因为有魔法,所以设计状态dx[i][j]表示物品i在当前用了j次魔法的情况下最小的购买价,这样才能当做背包来DP

dx怎么求呢?也不好求,所以这就是卡我的地方,我一开始还以为是DFS求

 

厚颜无耻的看题解……

你需要在枚举每个魔法w的时候都dp处理出 第w个魔法所需的前x个物品 用y次魔法 可以得到的最小购买价

设计状态ori[x][y]表示这样,每次枚举了一个魔法w都要求一次ori,注意y≤枚举的魔法次数

然后DP一波ori,这个很简单,写过几道提高水平的DP就会求

然后用ori[w需要的物品总数][枚举魔法次数-1]更新dx[w产成品][枚举的魔法次数]

·

这样我们就有了dx

xjb背包即可.XXXD

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<iterator>
using namespace std;

struct magic_s
{
	int needs[70],neednum;
	int prod;
};
magic_s mag[250]={0};
int buys[70]={0},sell[70]={0};
int n,kx,v,m,cache1=0,cache2=0;
int dx[70][40]={0},ori[70][40];
int dp[40][1010]={0};
//n->70   m->250  v->1010  k->40

inline void readx(int& x)
{
	x=0; int k=1; register char ch=0;
	while (ch<'0' || ch>'9') { ch=getchar(); if (ch=='-') k=-1; }
	while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
	x*=k;
}

int main()
{	
	readx(n); readx(m); readx(v); readx(kx);
	for (int i=1;i<=n;i++) { readx(buys[i]); readx(sell[i]); }
	for (int i=1;i<=m;i++)
	{
		readx(mag[i].prod); readx(mag[i].neednum);
		for (int j=1;j<=mag[i].neednum;j++) readx(mag[i].needs[j]);
	}
	
	for (int i=1;i<=n;i++)
		for (int j=0;j<=kx;j++) dx[i][j]=buys[i];
	
	for (int i=1;i<=kx;i++)
	{
		for (int j=1;j<=m;j++)//current magic
		{
			for (int k=1;k<=mag[j].neednum;k++) //origin things
			{
				for (int l=0;l<kx;l++)//pre-used magic
				{
					ori[k][l]=2*1e9;
					for (int o=0;o<=l;o++)//current uesd
						ori[k][l]=min(ori[k][l],ori[k-1][l-o]+dx[mag[j].needs[k]][o]);
				}
			}
			
			dx[mag[j].prod][i]=min(dx[mag[j].prod][i],ori[mag[j].neednum][i-1]);//update current DX
		}
	}
	
	for (int i=1;i<=n;i++)
		for (int j=0;j<=kx;j++)
			for (int l=0;l<=j;l++)
			{
				for (int o=v;o>=dx[i][l];o--)
				{
					dp[j][o]=max(dp[j][o],dp[j-l][o-dx[i][l]]+sell[i]-dx[i][l]);
				}
			}
	
	printf("%d\n",dp[kx][v]);
	return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

This site uses Akismet to reduce spam. Learn how your comment data is processed.