http://hihocoder.com/problemset/problem/1091
Little Ho is obsessed with a computer game called "Clicker". In this game player spends coins to raise his heroes' level and gains more coins by sending his heroes to defeat monsters. At the beginning all Little Ho's heroes are of level 0 and can do 0 damage to monsters. Raising ith hero from level 0 to level 1 costs Bi coins. Every time raising a hero to the next level costs 1.07 times(round down to the neareast integer) as much as previous time. So Raising ith hero from level X to level X+1 will cost [1.07...[1.07[1.07Bi]]...](repeat X times) coins where "[]" is the rounding function. Raising ith hero to one upper level can also raise his damage by Ai. So raising ith hero to level X will raise his damage to X*Ai.
Given the amount of coins Little Ho has, you are to calculate what is the maximum total damage can be reached by optimizing coin usage.
Line 1: Two possitive integers N(1 <= N <= 30), M(1 <= M <= 20000). N is the number of heroes and M is the number of coins.
Line 2~N+1: Each line contains two possitive integers A(1 <= A <= 1000) and B(1 <= B <= 8000) representing a hero. A is the damage factor and B is the number of coins needed to raise his level from 0 to 1.
Line 1: One integer, the maximum total damage.
Hero 1 is raised to level 1, 10 damage, by 40 coins.
Hero 2 is raised to level 2, 50 damage, by 124(60+64) coins.
样例输入 2 170 10 40 25 60 样例输出 60题意分析：
将金币用于提升英雄的攻击力，每提升一级消耗的金币是上一次的1.07(取整)倍。在给定的金币总数量、英雄个数、每个英雄对应的攻击力提升值和消耗的金币基数下。求总攻击力的最大值。
这是一道泛化的背包问题。
关于背包问题的讲解：背包问题九讲
关于本题更详细的分析：http://hihocoder.com/discuss/question/2640/
题解
#include <iostream> #include <algorithm> #include <vector> using namespace std; int main() { int i, n, m, bi, sum, maxk; cin >> n >> m; vector<int> a(n); vector<vector<int>> b(n,vector<int>(2,0)), dp(n + 1,vector<int> (m + 1,0)); for (i = 0; i < n; ++i) { cin >> a[i] >> b[i][1]; bi = sum = b[i][1]; while (sum + bi*1.07 < m) { bi *= 1.07; sum += bi; b[i].push_back(sum); } } for (i = 0; i < n; ++i) { maxk = b[i].size(); for (int j = 1; j <= m; ++j) { for (int k = 0; k<maxk; k++) { if (j < b[i][k]) break; dp[i+1][j] = max(dp[i+1][j], dp[i][j - b[i][k]] + k*a[i]); } } } cout << dp[n][m] << endl; return 0; } 代码剖析二维数组b存放消耗值，对于每一个英雄i,b[i][0]=0,表示不提升英雄i的等级，b[i][1]=给定的消耗基值，b[i][j]表示提升英雄i到等级j需要的金币。
dp[i][j]表示消耗j个金币处理完第i个英雄所能获得的最大攻击力。
关键代码：
dp[i + 1][j] = max(dp[i + 1][j], dp[i][j - b[i][k]] + k*a[i]); 表示消耗j金币处理完第i+1个英雄所能获得的最大攻击力，由当前值与提升英雄i等级到k级所能获得的最大攻击力中选最大值