思路就是如果报销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