题解：暗黑破坏神

• 题目
  • 【问题描述】
  • 【输入】
  • 【输出】
  • 【输入输出样例】
• 解析
  • 法一：
  • 法二：
• 代码：

题目

【问题描述】

游戏的主人公有n 个魔法，每个魔法分为若干个等级，第i 个魔法有p[i]个等级，每个魔法的每个等级都有一个效果值，一个j 级的i 种魔法的效果值为w[i,j]，魔法升一级需要一本相应的魔法书，购买魔法书需要金币，第i 个魔法的魔法书价格为c[i]，而小x 只有m 个金币。
你的任务就是帮助小x 决定如何购买魔法书才能使所有魔法的效果值之和最大，开始的时候所有魔法都是0 级，效果值为0。

【输入】

第一行用空格隔开的两个正整数n 和m，表示魔法的总数和金币的数量。
以下n 行，描述n 个魔法，第i+1 行描述第i 个魔法，均为整数。格式如下：
C[i] p[i] w[i,1] w[i,2] w[i,3]…w[i,p[i]]。

【输出】

输出只有一行一个整数，表示最大的魔法效果总和。

【输入输出样例】

diablo.in

3 10
1 3 1 2 2
2 3 2 4 6
3 3 2 1 10

diablo.out

11 

解析

这道题在正常的dp上没有任何困难，主要的问题在于输出路径：

法一：

for (int i = m; i >= 1; i--)
	if (maxn <= f[i]) {
		maxn = f[i];
		j = i;
	}
for (int i = n; i >= 1; i--) {
	road[i] = d[i][j];
	j-=road[i] * c[i];
}
for (int i = 1; i <= n; i++)
	printf("%d\n",road[i]);

法二：

递归输出

void print(int k,int left) {
    if(k == 0) return;
    print(k - 1,left - num[k][left] * c[k]);
    printf("%d\n" ,num[k][left]);
}

代码：

#include
using namespace std;
int n,m,tot,c[1010],v[50010],w[50010],p[1010][500],f[52000],d[1010][510],road[1010];
int num[1001][1001];
void print(int k,int left) {
    if(k == 0) return;
    print(k - 1,left - num[k][left] * c[k]);
    printf("%d\n" ,num[k][left]);
}
int main() {
    scanf("%d%d",&n,&m);
    for (int i = 1; i <= n; i++) {
	    scanf("%d%d",&c[i],&p[i][0]);
	    for (int j = 1; j <= p[i][0]; j++) {
		    int value;
		    scanf("%d",&value);
		    w[++tot] = j * c[i];
		    v[tot] = value;
		    p[i][j] = tot;
	    }
    }
    for (int i = 1; i <= n; i++) {
	    for (int j = m; j >= 0; j--) {
		    for (int k = 1; k <= p[i][0]; k++) {
			    if (j - w[p[i][k]] >= 0) {
				    if (f[j] < f[j - w[p[i][k]]] + v[p[i][k]]) {
					    f[j] = f[j - w[p[i][k]]] + v[p[i][k]];
					    d[i][j] = k;
					    num[i][j] = k;
				    }
			    }
		    }
	    }
    }
    printf("%d\n",f[m]);
    int j;
    int maxn = 0;
    int pl = m;
    while(f[pl] == f[pl - 1]) pl--;
    print(n,pl);
    return 0;
}
/*
3 10
1 3 1 2 2
2 3 2 4 6
3 3 2 1 10

11
1
0
3
*/