← INDEX DOCUMENT

【计蒜客】游戏

概述

题目描述：

小 A 在完成一天的刷题计划之后打开了一款游戏。

在这个游戏中，每个角色有 n 种技能，每种技能有 p[i] 个等级，技能的不同等级对应了不同的能力值，其中第 i 个技能如果升级到 j 级的话，那么该技能的能力值就变为 w[i][j]，第 i 个技能升级一级需要的技能点数为 c[i]。

小A 当前的技能点数为 m，你的任务就是使用不超过 m 的技能点数，让角色 n 个技能的能力值之和最大。

注意，刚开始时，每个技能的等级都为 0。
输入格式

第一行为两个整数 n,m (0<n≤100, 0<m≤500)。

接下来 n 行，描述 n 个技能的信息，其中第 i 行的输入格式为:

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

其中 0<c[i]≤10, 0<p[i]≤500保证输入和输出的数据都在 int 的范围内。
输出格式

第一行输出一个整数，为最大的能力值。

之后 n 行，每行输出一个整数，表示将第 i 个技能升级到多少级。

如果有多解 输出消耗技能点数最少的一组，若仍有多解，那么优先让靠前的技能的等级较低。

思路：

很明显是多重背包，难点在于如何记录。设一个f[i][j]数组代表前i个技能在不超过j点的情况下最大能力值,易得状态转移方程:f[i][j]=max(f[i][j],f[i-1][j-k*c[i]]+w[i][k]]
再设一个g[i][j]代表第i个技能在不超过j点的情况下最大等级
求出达到最大收益的最小花费mm，再用mm和g数组倒推出加点情况，存到ans数组中逆序输出即可

code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <bits/stdc++.h>
using namespace std;
int f[101][501];
int g[101][501];
int w[101][51];
int c[101];
int p[101];
int ans[101];
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>c[i]>>p[i];
        for(int j=1;j<=p[i];j++) cin>>w[i][j];
    }
//in
    for(int i=1;i<=n;i++){
        f[i][0]=0;
        for(int j=1;j<=m;j++){
            int nk=0;
            for(int k=0;k<=p[i];k++){
            	if(j>=k*c[i])
                if(f[i][j]<f[i-1][j-k*c[i]]+w[i][k])
                f[i][j]=f[i-1][j-k*c[i]]+w[i][k],nk=k;
            }
            g[i][j]=nk;
        }
    }
//dp
    int mm=m;
    while(f[n][mm]==f[n][mm-1]) mm--;
    cout<<f[n][m]<<endl;
    for(int i=n;i>=1;i--){
    	ans[n-i+1]=g[i][mm];
    	mm-=g[i][mm]*c[i];
	}
	for(int i=n;i>=1;i--){
		cout<<ans[i]<<endl;
	}
}
//out