这题是显然的dp
设dp[i][j][k]为考虑到第i个商人(第i个商人已经处理完),当前有j个金币和k个银币时,最多能买到多少纪念品
1.不买第i个纪念品,dp[i][j][k]=max(dp[i][j][k],dp[i-1][j][k])
2.用金币买第i个纪念品,dp[i][j][k]=max(dp[i][j][k],dp[i-1][j+1][k-get*pack[i]]+1)
get指的是通过商人的种类算出的商人会给你的钱袋数,pack[i]表示第i个商人一个钱袋里装多少银币
当k-get*pack[i]>=price[i]且第i个商人是generous时,不能用金币购买
3.用银币买第i个纪念品,dp[i][j][k]=max(dp[i][j][k],dp[i-1][j][k+price[i]]+1)
注意数组要滚动
我做这题的时候总是TLE,后来发现在循环里判断s[i]=="generous","greedy","honest"非常慢,因为是字符串的比较
所以提前把类型转换成数字后判断效率提升8倍左右
复制代码
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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86#include <cstdio> #include <iostream> #include <cstring> #include <string> #include <algorithm> #include <cstdlib> #include <utility> #include <stack> #include <queue> #include <deque> #include <set> #include <map> #include <vector> #include <cmath> #define Pair pair<int,int> #define LOWBIT(x) x & (-x) #define LL long long #define mp make_pair #define pb push_back #define x first #define y second using namespace std; const int MOD=1e9+7; const int INF=0x7ffffff; const int magic=348; const double eps=1e-9; int g,c,n; string s[101]; int type[101]; int pack[101],price[101]; int dp[2][101][20148]; int main () { int i,j,k; scanf("%d%d%d",&g,&c,&n); for (i=1;i<=n;i++) { cin>>s[i]>>pack[i]>>price[i]; if (s[i]=="generous") type[i]=1; if (s[i]=="greedy") type[i]=2; if (s[i]=="honest") type[i]=3; } for (i=0;i<=1;i++) for (j=0;j<=c;j++) for (k=0;k<=20100;k++) dp[i][j][k]=-INF; dp[0][c][0]=0; int p1=0,p2=1; int remain,get; double t; int ans=0; for (i=1;i<=n;i++) { for (j=0;j<=c;j++) for (k=0;k<=min(i*100,10010);k++) { dp[p2][j][k]=dp[p1][j][k]; /*if (k+price[i]<=20100) { dp[p2][j][k]=max(dp[p2][j][k],dp[p1][j][k+price[i]]+1); if (type[i]==1 && dp[p1][j][k+price[i]]>=0) { if (i==n) ans=max(ans,dp[p2][j][k]); continue; } }*/ remain=g-price[i]; t=remain*1.0/pack[i]; if (type[i]==2) get=int(t); if (type[i]==3) get=int(t+0.5); if (type[i]==1) { get=int(t+1); if (t==int(t)) get--; } if (j+1<=c && k-get*pack[i]>=0) if (!(type[i]==1 && k-get*pack[i]>=price[i]))dp[p2][j][k]=max(dp[p2][j][k],dp[p1][j+1][k-get*pack[i]]+1); if (k+price[i]<=min(i*100,10010)) dp[p2][j][k]=max(dp[p2][j][k],dp[p1][j][k+price[i]]+1); if (i==n) ans=max(ans,dp[p2][j][k]); } p1^=1;p2^=1; } printf("%dn",ans); return 0; }
最后
以上就是哭泣咖啡最近收集整理的关于Codeforces GYM 100753J: Souvenirs 题解的全部内容,更多相关Codeforces内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复