http://openoj.a
waysoft.com/JudgeOnline/problem.php?id=1634
暗黑破坏神
Description
无聊中的小x玩起了Diablo I...
游戏的主人公有n个魔法
每个魔法分为若干个等级，第i个魔法有p[i]个等级(不包括0)
每个魔法的每个等级都有一个效果值，一个j级的i种魔法的效果值为w[i][j]
魔法升一级需要一本相应的魔法书
购买魔法书需要金币，第i个魔法的魔法书价格为c[i]
而小x只有m个金币(好孩子不用修改器)
你的任务就是帮助小x决定如何购买魔法书才能使所有魔法的效果值之和最大
开始时所有魔法为0级 效果值为0
Input
第一行 用空格隔开的两个整数n(0<n<=100) m(0<m<=500)
以下n行 描述n个魔法
第i+1行描述 第i个魔法 格式如下(0<p[i]<=50, 0<c[i]<=10)
c[i] p[i] w[i][1] w[i][2] ... w[i][p[i]]
Output
第一行输出一个整数，即最大效果值。(保证输入数据和最终结果在longint范围内)
以后n行输出你的方案：
第i+1行有一个整数v[i] 表示你决定把第i个魔法学到v[i]级
如果有多解 输出花费金币最少的一组
如果还多解 输出任意一组
Sample Input
3 10
1 3 1 2 2
2 3 2 4 6
3 3 2 1 10
Sample Output
11
1
0
3
#include <iostream>
#include <fstream>
#include <algorithm>
#include <string>
#include <set>
//#include <map>
#include <queue>
#include <utility>
#include <iomanip>
#include <stack>
#include <list>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <ctype.h>
using namespace std;
#define inf 0x3fffffff
int dp[105][505], w[105], M, num, mark[105][505], v[105], c[105];
void gp1_pack (int i, int cost) //二维分组背包
{
int j, k;
for (j = 1; j <= M; j++)
{
for (k = 0; k <= num && j >= k*cost; k++)
{
if (dp[i][j] < dp[i-1][j-k*cost] + w[k])
{
dp[i][j] = dp[i-1][j-k*cost] + w[k];
mark[i][j] = k; //记录魔法级数【k：第i组的第k个物品】
}
}
}
}
int main()
{
int n, i, j, maxs, vj;
while (~scanf ("%d%d", &n, &M))
{
w[0] = 0;
for (i = 1; i <= n; i++)
{
scanf ("%d%d", c+i, &num);
for (j = 1; j <= num; j++)
scanf ("%d", w+j);
gp1_pack (i, c[i]); //每一组进行一次背包
}
maxs = 0;
for (j = M; j >= 0; j--) //寻找花费最小价值最大的路径终点
if (maxs <= dp[n][j])
maxs = dp[n][j], vj = j;
j = vj; //关键终点
for (i = n; i > 0; i--)
{
v[i] = mark[i][j]; //记录路径
j = j - c[i] * v[i]; //返回上一层
}
printf ("%d\n", maxs);
for (i = 1; i <= n; i++) //路径输出
printf ("%d\n", v[i]);
}
return 0;
}
相关文章
