学步园

暗黑破坏神(diablo.pas)

无聊中的小x玩起了Diablo I...

游戏的主人公有n个魔法

每个魔法分为若干个等级，第i个魔法有p[i]个等级(不包括0)

每个魔法的每个等级都有一个效果值，一个j级的i种魔法的效果值为w[i][j]

魔法升一级需要一本相应的魔法书

购买魔法书需要金币，第i个魔法的魔法书价格为c[i]

而小x只有m个金币(好孩子不用修改器)

你的任务就是帮助小x决定如何购买魔法书才能使所有魔法的效果值之和最大

开始时所有魔法为0级 效果值为0

输入(diablo.in)

第一行 用空格隔开的两个整数n m

以下n行 描述n个魔法

第i+1行描述 第i个魔法 格式如下

c[i] p[i] w[i][1] w[i][2] ... w[i][p[i]]

输出(diablo.out)

第一行输出一个整数，即最大效果值。

以后n行输出你的方案：

第i+1行有一个整数v[i] 表示你决定把第i个魔法学到v[i]级

如果有多解 输出花费金币最少的一组

如果还多解 输出任意一组

样例

约定

0<n<=100

0<m<=500

0<p[i]<=50

0<c[i]<=10

保证输入数据和最终结果在longint范围内

一道sb的dp而已

f[i][j]表示前i种魔法用j金币的最大收益

然后变sb背包dp了

最后再保存一下f[i][j]从f[i-1][???]转移而来就可以打出方案

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#include<deque>
#include<set>
#include<map>
#include<ctime>
#define LL long long
#define inf 0x7ffffff
#define pa pair<int,int>
#define pi 3.1415926535897932384626433832795028841971
using namespace std;
pa f[110][510];
LL c[1000];
LL p[1000];
LL w[100][100];
LL zhan[1000];
LL n,m,top;
inline LL read()
{
    LL x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int main()
{
	freopen("diablo.in","r",stdin);
	freopen("diablo.out","w",stdout);
	n=read();m=read();
	for (int i=1;i<=n;i++)
	  {
	  	c[i]=read();
		p[i]=read();
	  	for (int j=1;j<=p[i];j++)w[i][j]=read();
	  }
	for (int i=1;i<=n;i++)
	  for(int j=m;j>=0;j--)
	    {
	    	f[i][j].first=f[i-1][j].first;
	    	f[i][j].second=0;
	    	for (int k=1;k<=min(j/c[i],p[i]);k++)
	    	  if (f[i-1][j-c[i]*k].first+w[i][k]>f[i][j].first)
	    	  {
	    	  	f[i][j].first=f[i-1][j-c[i]*k].first+w[i][k];
	    	  	f[i][j].second=k;
	    	  }
	    }
	LL tot=-1,sav=-1,floor=n;
	for(int i=1;i<=m;i++)
	  {
	  	if (f[n][i].first>tot)
	  	{
	  		tot=f[n][i].first;
	  		sav=i;
	  	}
	  }
	cout<<tot<<endl;
	while (floor)
	{
		zhan[++top]=f[floor][sav].second;
		sav-=f[floor][sav].second*c[floor];
		floor--;
	}
	while (top)cout<<zhan[top--]<<endl;
}