思路就是如果报销n张就必须报销n-1张。
j表示可以报销的张数。
状态方程：dp[j] = Max(dp[j], dp[j-1]+v[i]);//状态方程
恶心地方:有这样的输入数据 3
A:100 A:200 A:300
http://acm.hdu.edu.cn/showproblem.php?pid=1864
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 14504 Accepted Submission(s): 4084
|
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 |
#include<stdio.h>#include<string.h>double
Max(double
a, double
b){ if
(a > b) { return
a; } return
b;}int
main(){ int
n,m,i,j,flag,num; double
v[100],dp[1001]; double
q,z,asum,bsum,csum,sum,ans; char
ch; for(;;) { memset(v, 0, sizeof(v)); memset(dp,0,sizeof(dp)); scanf("%lf%d",&q,&n); if(n==0) break; num=0;//就记录几种可以报销 for
(i = 0; i < n; ++i) { flag = 1; sum = 0; asum = 0;//记录每一类总的物品价值。 bsum = 0; csum = 0; scanf("%d", &m); for
(j = 0;j<m; ++j) { getchar(); scanf("%c:%lf", &ch,&z); if
(ch != ‘A‘ && ch != ‘B‘
&& ch != ‘C‘
|| z > 600.0) { flag = 0; break; } else
if (ch == ‘A‘) { asum += z; } else
if (ch == ‘B‘) { bsum += z; } else
if (ch == ‘C‘) { csum += z; } } sum=asum+bsum+csum; if
(flag && sum <= 1000.0 && asum <= 600.0 && bsum <= 600.0 && csum <= 600.0)//符合报销的条件 { v[num]=sum; num ++; } } for
(i = 0; i <= num; ++i)//为什么要等于m保证的dp[1]的值不会被重新输入。 { for
(j = num; j >= 1;j--) { if
(j == 1|| dp[j - 1] >0&&dp[j-1]+v[i]=q) { dp[j] = Max(dp[j], dp[j-1]+v[i]);//状态方程 } } } ans = 0; for
(i = 0; i <= num; ++i)//找出最大的报销就行。 { if
(ans < dp[i]) { ans = dp[i]; } } printf("%.2lf\n", ans); } return
0;} |
原文：http://www.cnblogs.com/cancangood/p/3558464.html