描述
一年一度的暴雪嘉年华（BlizzCon’16）即将盛大开幕，作为贪玩的助教小J，自然翘掉了程设期末前往参加。本届嘉年华为期m天，在这24*m小时的时间里，观众买券入场后方可体验各种免费及付费的游戏项目。参加本届嘉年华，首先需要在现场购买入场券，现场可以购买的入场券有三种，允许叠加购买使用：
-
单日券：售价100美金，购买后可以进入会场游玩24小时；
-
双日券：售价150美金，购买后可以进入会场游玩48小时；
-
三日券：售价200美金，购买后可以进入会场游玩72小时。
买券进入会场后，就可以在规定时间内体验各种游戏项目了，会场内总共有n个游戏项目。对于小J来说，每个游戏项目i都有个乐趣值H_i，每体验一次该游戏项目，他就能获得这么多的乐趣。体验游戏项目可能要额外付费，每体验一次游戏项目i，就收费C_i美金；如果是免费项目，C_i＝0。每个游戏项目都有其固定的体验时间，每体验一次游戏项目i所花费的时间是T_i个小时。此外，某些游戏项目会限制玩家全程只能体验一次（即使它是收费项目），但其它游戏项目则允许玩家无限次体验。
一开始在入场之前，小J有s美元的现金，这些钱既要用来购买入场券，又可用于体验收费游戏项目。现在请你替小J购买合适的入场券组合，并选取需要体验的游戏项目，使得小J利用不超过s美元体验游戏所获得的乐趣值之和最大，输出该最大的乐趣值之和。
题目中忽略体验游戏之外的时间花费，游戏项目允许跨天进行体验（小J在体验游戏时，从来不需要休息、吃饭或上厕所）。
输入
程序输入的第一行是三个正整数m, n, s，表示嘉年华举办天数、游戏项目数及小J一开始的美元现金。
接下来n行，每行包括三个非负整数H_i, C_i, T_i和一个单词用于描述第i个游戏项目，如果单词是limited，则表示游戏项目仅允许体验一次；如果单词是unlimited，则表示游戏项目允许无限次体验。
对于所有的数据，有：
1<=m, n<=100
1<=s, T_i<=1000
0<=H_i, C_i<=1000 (i<=n)。
输出
程序输出仅包含一个非负整数，表示小J在限定条件下所能获取的最大的乐趣值之和。
样例输入
5 5 312
150 0 24 limited
200 1 48 limited
900 0 97 limited
3 3 3 unlimited
50 50 1 unlimited
样例输出
359
提示样例说明：
在5天的活动当中，小J购买了一张单日券和一张三日券（或者两张双日券），得到了96个小时的入场游玩时间。在5个游戏项目当中，他体验了游戏1、游戏2、并重复体验了3遍游戏4，总花费为100+200+0+1+3*3=310美元，实际游玩24+48+3*3=81小时，获得的乐趣值之和为150+200+3*3=359。
1 #include <cstdio> 2 #include <string> 3 #include <memory.h> 4 #include <algorithm> 5 #include <stdlib.h> 6 #include <math.h> 7 #include <iostream> 8 #include<queue> 9 #include <set> 10 using namespace std; 11 12 int m, n, s; 13 int limit[105][3], unlimit[105][3]; 14 int sumlimi = 0, sumun = 0; 15 int dp[2][2405][1005];//0:limit 1:unlimit time money 16 int maxday; 17 int ans = 0; 18 19 void solve() { 20 for (int day = 1; day <= maxday; day++) { 21 memset(dp, 0, sizeof(int) * 2 * 2405 * 1005); 22 int money = s; 23 money -= day / 3 * 200+(day%3/2*150)+(day%3%2*100); 24 int time = 24 * day; 25 for(int i=1;i<=sumlimi;i++) 26 for(int j=time;j>=1;j--) 27 for (int k = money; k >= 0; k--) 28 if(k>=limit[i][1]&&j>=limit[i][2]) 29 dp[0][j][k] = max(dp[0][j][k],dp[0][j - limit[i][2]][k - limit[i][1]] + limit[i][0]); 30 for (int i = 1; i<=sumun; i++) 31 for (int j = 1; j<=time; j++) 32 for (int k = 0; k <=money; k++) 33 if (k >= unlimit[i][1] && j >= unlimit[i][2]) 34 dp[1][j][k] = max(dp[1][j][k],dp[1][j - unlimit[i][2]][k - unlimit[i][1]] + unlimit[i][0]); 35 for (int i = 0; i <= time; i++) 36 for (int j = 0; j <= money; j++) 37 ans = max(ans, dp[0][i][j] + dp[1][time - i][money - j]); 38 } 39 printf("%d ", ans); 40 } 41 42 int main() 43 { 44 scanf("%d%d%d", &m, &n, &s); 45 int _s = s; 46 maxday += _s / 200 * 3; 47 _s %= 200; 48 maxday += _s / 150 * 2; 49 _s %= 150; 50 maxday += _s / 100; 51 maxday = min(maxday, m); 52 for (int i = 1; i <= n; i++) { 53 int a, b, c; 54 scanf("%d%d%d", &a, &b, &c); 55 string ch; 56 cin >> ch; 57 if (ch == "limited") { 58 limit[++sumlimi][0] = a; 59 limit[sumlimi][1] = b; 60 limit[sumlimi][2] = c; 61 } 62 else { 63 unlimit[++sumun][0] = a; 64 unlimit[sumun][1] = b; 65 unlimit[sumun][2] = c; 66 } 67 } 68 solve(); 69 return 0; 70 }
忘清空dp数组debug一小时
思路：
部分完全背包＋01背包