描述 小Hi在游乐园中获得了M张奖券，这些奖券可以用来兑换奖品。
可供兑换的奖品一共有N件。第i件奖品需要Wi张奖券才能兑换到，其价值是Pi。
小Hi使用不超过M张奖券所能兑换到的最大奖品总价值是多少？
输入 第一行两个整数N，M。
接下来N行，每行两个整数Wi，Pi。
对于 50%的数据： 1≤N,M≤1000
对于 100%的数据： 1≤N,M≤100000, 1≤Pi,Wi≤10。
输出 一行一个整数，表示最大的价值。
样例输入 3 10 2 3 8 8 10 10 样例输出 11
#include <iostream> #include <string.h> #include <math.h> using namespace std; int main() { int N, M, u[11][11], dp[100005]; memset(u, 0, sizeof(u)); //string.h memset(dp, 0, sizeof(dp)); cin >> N >> M; int max_w = 0, max_p = 0; for (int i = 0; i < N; i++) { int w, p; cin >> w >> p; if (w > max_w) max_w = w; if (p > max_p) max_p = p; u[w][p]++; } for (int i = 1; i <= max_w; i++) { for (int j = 1; j <= max_p; j++) { int tem = 1; while (u[i][j] > 0) { int num; if (u[i][j] >= tem) { u[i][j] -= tem; num = tem; } else { num = u[i][j]; u[i][j] = 0; } tem *= 2; //2倍增长 for (int k = M; k >= i * num; k--) dp[k] = max(dp[k], dp[k - i * num] + j * num); } } } cout << dp[M] << endl; return 0; }为什么用二倍增长法？提高遍历效率。 这里以u[2][*]举例： M=10, 因为第一次更新时是 10->9->8->7->…2
hicode官网 http://hihocoder.com/hiho 转载于 https://www.cnblogs.com/wxyww/p/10313839.html
