DP入门题集

　　　　这段时间要开始刷dp了，记录点点滴滴。21:33:51

　　　　一.基础dp：

　　1.hdu.2602.Bone Collector.

　　这道是基础的01背包。

 1 #include<cstdio>
 2 #include<algorithm>
 3 using namespace std;
 4 const int MAXN=1000+10;
 5 int w[MAXN];
 6 int v[MAXN];
 7 int dp[MAXN];
 8 int main()
 9 {
10     int test;
11     scanf("%d",&test);
12     while(test--)
13     {
14         int n,V;
15         scanf("%d%d",&n,&V);
16         for(int i=1;i<=n;i++)
17             scanf("%d",&w[i]);
18         for(int i=1;i<=n;i++)
19             scanf("%d",&v[i]);
20         for(int j=0;j<=V;j++)
21             dp[j]=0;
22         for(int i=1;i<=n;i++)
23             for(int j=V;j>=v[i];j--)
24         {
25             dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
26         }
27         int ans=0;
28         for(int j=0;j<=V;j++)
29             if(dp[j]>ans)
30                 ans=dp[j];
31         printf("%d
",ans);
32     }
33     return 0;
34 }

View Code

　　2.poj.3624.Charm Bracelet.

　　基础01背包，注意下标的最大值为物品数还是背包容量最大值。

 1 #include<cstdio>
 2 #include<algorithm>
 3 using namespace std;
 4 const int MAXN=3410;
 5 const int MAXM=13000;
 6 int w[MAXN];
 7 int cost[MAXN];
 8 int dp[MAXM];
 9 int main()
10 {
11     int n,m;
12     while(scanf("%d%d",&n,&m)!=EOF)
13     {
14         for(int i=1;i<=n;i++)
15             scanf("%d%d",&cost[i],&w[i]);
16         for(int j=0;j<=m;j++)
17             dp[j]=0;
18         for(int i=1;i<=n;i++)
19             for(int j=m;j>=cost[i];j--)
20                 dp[j]=max(dp[j],dp[j-cost[i]]+w[i]);
21         int ans=0;
22         for(int i=0;i<=m;i++)
23             if(dp[i]>ans)
24                 ans=dp[i];
25         printf("%d
",ans);
26     }
27     return 0;
28 }

View Code

　　3.hdu.2546.饭卡.

　　先预留5元去买最贵的菜，注意n==0 时结束。

 1 #include<cstdio>
 2 #include<algorithm>
 3 using namespace std;
 4 const int maxn=1000+5;
 5 const int maxm=1000+5;
 6 int a[maxn];
 7 int dp[maxm];
 8 int main()
 9 {
10     int n;
11     while(scanf("%d",&n)!=EOF)
12     {
13         if(n==0)
14             break;
15         for(int i=1;i<=n;i++)
16             scanf("%d",&a[i]);
17         int m;
18         scanf("%d",&m);
19         if(m<5)
20             printf("%d
",m);
21         else
22         {
23             int mm=m-5;
24             sort(a+1,a+n+1);
25             for(int i=0;i<=mm;i++)
26                 dp[i]=0;
27             for(int i=1;i<n;i++)
28                 for(int j=mm;j>=a[i];j--)
29                     dp[j]=max(dp[j],dp[j-a[i]]+a[i]);
30             int ans=0;
31             for(int i=0;i<=mm;i++)
32                 if(dp[i]>ans)
33                     ans=dp[i];
34             printf("%d
",m-ans-a[n]);
35         }
36     }
37     return 0;
38 }

View Code

　　4.uva.562.Dividing Coins

　平衡问题，先累加硬币的总价值，然后sum/2，作为背包容量对n个硬币进行选择，求出其最大价值。

 1 #include<cstdio>
 2 #include<algorithm>
 3 using namespace std;
 4 const int MAXN=105;
 5 const int MAXM=30000;
 6 int dp[MAXM];
 7 int coin[MAXN];
 8 int main()
 9 {
10     int test;
11     scanf("%d",&test);
12     while(test--)
13     {
14         int n;
15         scanf("%d",&n);
16         int sum=0;
17         for(int i=1;i<=n;i++)
18         {
19             scanf("%d",&coin[i]);
20             sum+=coin[i];
21         }
22         int half=sum/2;
23         for(int i=0;i<=half;i++)
24             dp[i]=0;
25         for(int i=1;i<=n;i++)
26             for(int j=half;j>=coin[i];j--)
27                 dp[j]=max(dp[j],dp[j-coin[i]]+coin[i]);
28         int cnt=0;
29         for(int i=0;i<=half;i++)
30             if(dp[i]>cnt)
31                 cnt=dp[i];
32         half=sum-cnt;
33         int ans;
34         if(half>cnt)
35             ans=half-cnt;
36         else
37             ans=cnt-half;
38         printf("%d
",ans);
39     }
40     return 0;
41 }

View Code　　

　　5.hdu.2955.Robberies.

　被抓的概率比较难算，加之精度问题，所以转换为不被抓的概率。

　若以概率为代价，不是整数，无法作为下标，所以以银行总价值为背包容量，单个银行的储蓄为体积，以不被抓的概率作为价值。

 1 #include<cstdio>
 2 #include<algorithm>
 3 using namespace std;
 4 const int MAXN=105;
 5 const int MAXM=11000;
 6 double dp[MAXM];
 7 int money[MAXN];
 8 double pro[MAXN];
 9 int main()
10 {
11     int test;
12     scanf("%d",&test);
13     while(test--)
14     {
15         int n;
16         double P;
17         scanf("%lf%d",&P,&n);
18         P=1.0-P;
19         int sum=0;
20         for(int i=1;i<=n;i++)
21         {
22             scanf("%d%lf",&money[i],&pro[i]);
23             sum+=money[i];
24             pro[i]=1.0-pro[i];
25         }
26         for(int i=0;i<=sum;i++)
27             dp[i]=0;
28         dp[0]=1;
29         for(int i=1;i<=n;i++)
30             for(int j=sum;j>=money[i];j--)
31                 dp[j]=max(dp[j],dp[j-money[i]]*pro[i]);
32         int ans=0;
33         for(int i=0;i<=sum;i++)
34             if(dp[i]>=P&&i>ans)
35                 ans=i;
36         printf("%d
",ans);
37     }
38     return 0;
39 }

View Code

6.HDU1087

题意：在一串数列中，找出一串数字要严格递增的子序列（不用连续），使得该子序列的和为最大值。

dp[i]表示以a[i] 为结束元素的子序列中和最大的一组的和。

 1 #include<iostream>
 2 #include<algorithm>
 3 using namespace std;
 4 
 5 const int maxn=1010;
 6 
 7 int dp[maxn];
 8 
 9 int a[maxn];
10 
11 int main()
12 {
13     int n;
14     while(cin>>n)
15     {
16         if(!n)
17             break;
18 
19         for(int i=1;i<=n;i++)
20             cin>>a[i];
21 
22         for(int i=1;i<=n;i++)
23             dp[i]=a[i];
24 
25         for(int i=1;i<=n;i++)
26             for(int j=1;j<i;j++)
27                 if(a[j]<a[i]&&dp[j]+a[i]>dp[i])
28                     dp[i]=dp[j]+a[i];
29 
30         int ans=0;
31         for(int i=1;i<=n;i++)
32             if(ans<dp[i])
33                 ans=dp[i];
34 
35         cout<<ans<<endl;
36     }
37     return 0;
38 }

View Code

7.HDU 2571 命运

这道题就是给出一个n*m的矩阵，每个矩阵有一个价值(也可以为负)

规定小明在这个矩阵内可以从(x,y)走到(x+1,y) ,(x,y+1), (x,y*k) ,其中K>1

即小明也可以从该点走到向下一格，或者向右一格，或者向右走到该行的列数是当前列数的倍数的格子。

然后现在小明要从(1,1)走到(n,m)

问最大的价值为多少

dp[i][j]为走到(i,j)时的最大价值

注意初始化，为-inf，除了dp[1][1]=a[1][1]

刚开始初始化为0，wa了。

先递推第一行和第一列，然后再递推后面。

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<algorithm>
 5 using namespace std;
 6 
 7 const int inf=0x3f3f3f3f;
 8 const int maxn=23;
 9 const int maxm=1010;
10 
11 int dp[maxn][maxm];
12 int a[maxn][maxm];
13 
14 int main()
15 {
16     //freopen("in.txt","r",stdin);
17 
18     int test;
19     cin>>test;
20     while(test--)
21     {
22         int n,m;
23         cin>>n>>m;
24         for(int i=1;i<=n;i++)
25             for(int j=1;j<=m;j++)
26                 cin>>a[i][j];
27         
28         //刚开始初始化为0，错了，考虑清楚再做题
29         for(int i=1;i<=n;i++)
30             for(int j=1;j<=m;j++)
31                 dp[i][j]=-inf;
32 
33         dp[1][1]=a[1][1];
34         for(int i=2;i<=n;i++)
35             dp[i][1]=dp[i-1][1]+a[i][1];
36         for(int j=2;j<=m;j++)
37         {
38             for(int k=1;k<j;k++)
39                 if(j%k==0)
40                     dp[1][j]=max(dp[1][j],dp[1][k]+a[1][j]);
41             dp[1][j]=max(dp[1][j],dp[1][j-1]+a[1][j]);
42         }
43         for(int i=2;i<=n;i++)
44             for(int j=2;j<=m;j++)
45             {
46                 dp[i][j]=max(dp[i][j-1],dp[i-1][j])+a[i][j];
47                 for(int k=1;k<j;k++)
48                     if(j%k==0)
49                         dp[i][j]=max(dp[i][j],dp[i][k]+a[i][j]);
50             }
51 
52         cout<<dp[n][m]<<endl;
53     }
54     return 0;
55 }

View Code

8.HDU 1069 Monkey and banana

题意：有n种箱子，问最多能把箱子堆得多高，要求：上面的箱子的长和宽都要严格小于下面的长和宽。

排序+最大子序列

每种箱子，有x,y,z，全排列6种，所以可以看作是有6n个箱子。

1.按照长，宽从小到大排列

2.dp[i] 表示以第i个箱子为底，最高的高度，

则dp[i]初始化为box[i].z，即第i个箱子上面没有其他箱子时的高度。

i：1-->n

dp[i]=box[i].z; // 初始化

j：-->i-1 // 查看一次

if( 可以放 )

dp[i]=max(dp[i],dp[j]+box[i].z);

若第j 个箱子满足放在i上的条件。

 1 #include<iostream>
 2 #include<cstring>
 3 #include<algorithm>
 4 using  namespace std;
 5 
 6 const int maxn=33;
 7 
 8 int dp[maxn*6];
 9 
10 struct Box
11 {
12     int x,y,z;
13 }box[maxn*6];
14 
15 int tot;
16 
17 void addedge(int x,int y,int z)
18 {
19     box[tot].x=x;
20     box[tot].y=y;
21     box[tot++].z=z;
22 }
23 
24 bool cmp(Box a,Box b)
25 {
26     if(a.x==b.x)
27         return a.y<b.y;
28     return a.x<b.x;
29 }
30 
31 int main()
32 {
33     int n;
34     int cas=1;
35 
36     while(cin>>n)
37     {
38         if(!n)
39             break;
40 
41         int a,b,c;
42 
43         tot=1;
44 
45         for(int i=1;i<=n;i++)
46         {
47             cin>>a>>b>>c;
48 
49             addedge(a,b,c);
50             addedge(a,c,b);
51             addedge(b,a,c);
52             addedge(b,c,a);
53             addedge(c,a,b);
54             addedge(c,b,a);
55         }
56 
57         tot--;
58 
59         sort(box+1,box+tot+1,cmp);
60 
61         for(int i=1;i<=tot;i++)
62             dp[i]=box[i].z;
63 
64         for(int i=1;i<=tot;i++)
65             for(int j=1;j<i;j++)
66              if(box[j].x<box[i].x&&box[j].y<box[i].y)
67                 dp[i]=max(dp[i],dp[j]+box[i].z);
68 
69         int ans=0;
70 
71         for(int i=1;i<=tot;i++)
72             if(ans<dp[i])
73                 ans=dp[i];
74 
75         cout<<"Case "<<cas++<<": maximum height = "<<ans<<endl;
76     }
77     return 0;
78 }

View Code

9.HDU 1171 Bing Event in HDU

题意：n种物品，每种的价值为val，有num个，

现在要将所有物品分成A,B 2份，要求，A,B尽量相等，但要保证A>=B

化为01背包

B=sum/2

将B作为背包最大容量

 1 #include<iostream>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 
 6 const int maxn=5100;
 7 const int maxv=125100;
 8 
 9 int dp[maxv];
10 int v[maxn];
11 
12 int main()
13 {
14     int n;
15     while(cin>>n)
16     {
17         if(n<0)
18             break;
19 
20         int tot=1;
21 
22         int val,num;
23 
24         for(int i=1;i<=n;i++)
25         {
26             cin>>val>>num;
27             for(int j=1;j<=num;j++)
28                 v[tot++]=val;
29         }
30 
31         int sum=0;
32 
33         for(int i=1;i<tot;i++)
34             sum+=v[i];
35 
36         int B=sum/2;
37 
38         memset(dp,0,sizeof(dp));
39 
40         for(int i=1;i<tot;i++)
41             for(int j=B;j>=v[i];j--)
42         {
43             dp[j]=max(dp[j],dp[j-v[i]]+v[i]);
44         }
45 
46         int ans_b=0;
47         for(int i=0;i<=B;i++)
48             if(dp[i]>ans_b)
49                 ans_b=dp[i];
50 
51         cout<<sum-ans_b<<" "<<ans_b<<endl;
52     }
53     return 0;
54 }

View Code

10.HDU 2084 数塔

先初始化最后一行，然后从后往前递推

 1 #include<iostream>
 2 #include<algorithm>
 3 using namespace std;
 4 
 5 const int maxn=105;
 6 
 7 int a[maxn][maxn];
 8 int dp[maxn][maxn];
 9 
10 int main()
11 {
12     int test;
13     cin>>test;
14     while(test--)
15     {
16         int n;
17         cin>>n;
18         for(int i=1;i<=n;i++)
19             for(int j=1;j<=i;j++)
20                 cin>>a[i][j];
21 
22         for(int j=1;j<=n;j++)
23             dp[n][j]=a[n][j];
24         for(int i=n-1;i>0;i--)
25             for(int j=1;j<=i;j++)
26                 dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+a[i][j];
27 
28         cout<<dp[1][1]<<endl;
29 
30     }
31     return 0;
32 }

View Code

11.HDU 1176 免费馅饼

这道题和数塔一样de

把时间看成行，点看成列，就是和数塔一样递推了

注意，这里把所有输入的点x++，是为了不用对边界的递推进行另外处理

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 
 6 const int maxT=100000+10;
 7 
 8 int dp[maxT][13];
 9 int a[maxT][13];
10 
11 int main()
12 {
13     int n;
14     while(scanf("%d",&n))
15     {
16         if(!n)
17             break;
18 
19         memset(a,0,sizeof(a));
20 
21         int t,x;
22         int maxt=0;
23         for(int i=1;i<=n;i++)
24         {
25             scanf("%d%d",&x,&t);
26             x++;
27             a[t][x]++;
28             if(t>maxt)
29                 maxt=t;
30         }
31 
32         for(int j=1;j<=11;j++)
33             dp[maxt][j]=a[maxt][j];
34 
35         for(int i=maxt-1;i>=0;i--)
36             for(int j=1;j<=11;j++)
37                 dp[i][j]=max(max(dp[i+1][j-1],dp[i+1][j]),dp[i+1][j+1])+a[i][j];
38 
39         printf("%d
",dp[0][6]);
40 
41     }
42     return 0;
43 }

78ms

12.HDU 1203 I need a offer

也是简单的01背包

至少一个学校offer的概率，就等于1-一个都没有的概率

注意2个小细节，写在注释

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 
 6 const int maxn=10000+10;
 7 
 8 double dp[maxn];
 9 double pro[maxn];  //申请不到的概率
10 int cost[maxn];
11 
12 int main()
13 {
14     int n,m;
15     while(scanf("%d%d",&n,&m))
16     {
17         if(!n&&!m)
18             break;
19 
20 
21         for(int i=1;i<=m;i++)
22         {
23             scanf("%d%lf",&cost[i],&pro[i]);
24             pro[i]=1.0-pro[i];
25         }
26 
27 
28         //刚开始用memset(dp,1.0,sizeof(dp));
29         //但是数组并没有被初始化为1.0
30         //注意这里，memset慎用
31 
32         for(int i=0;i<=n;i++)
33             dp[i]=1.0;
34 
35         for(int i=1;i<=m;i++)
36             for(int j=n;j>=cost[i];j--)
37                 dp[j]=min(dp[j],dp[j-cost[i]]*pro[i]);
38 
39         double ans=1.0;
40 
41         for(int i=0;i<=n;i++)
42             if(dp[i]<ans)
43                 ans=dp[i];
44 
45         //刚开始用printf("%.1f%
",100-ans*100);
46         //wa了
47         
48         printf("%.1f%%
",100-ans*100);
49 
50     }
51     return 0;
52 }

View Code

13.HDU2159 fate

好题

题意：小明升级需要n的经验，但是他的忍耐度只有m，每杀一只怪会减掉一些忍耐度，m用完了，小明就不再继续玩下去了，而且，小明最多只杀s只怪。

现在有k种怪，每种怪无数只，每种怪有相应的经验val，和忍耐度b

现在问小明能不能升级，能的话，最多还可以剩下多少忍耐度。

这道是2维代价的完全背包

经验n:价值

忍耐度m和杀怪数s：代价

 1 #include<iostream>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 
 6 const int maxn=105;
 7 
 8 int dp[maxn][maxn];   
 9 int val[maxn];   //相应的经验
10 int b[maxn];     //相应的忍耐度
11 
12 int main()
13 {
14     int n,m,kind,s;
15 
16     while(cin>>n)
17     {
18         cin>>m>>kind>>s;
19         for(int i=1;i<=kind;i++)
20             cin>>val[i]>>b[i];
21 
22         memset(dp,0,sizeof(dp));
23 
24 
25         //选择杀不杀第k种怪后，
26         //付出代价为i，杀的怪数为j时得到的最大经验为dp[i][j]
27         for(int k=1;k<=kind;k++)
28             for(int i=b[k];i<=m;i++)
29                 for(int j=1;j<=s;j++)
30                     dp[i][j]=max(dp[i][j],dp[i-b[k]][j-1]+val[k]);
31 
32         int ans=10000;
33         
34         //在得到的经验>=n的条件下付出的忍耐度i尽量小
35         //则剩下的忍耐度会尽量大
36         for(int i=0;i<=m;i++)
37             for(int j=0;j<=s;j++)
38                 if(dp[i][j]>=n&&i<ans)
39                     ans=i;
40 
41         ans=m-ans;  //求出剩下的忍耐度
42         if(ans<0)
43             cout<<-1<<endl;
44         else
45             cout<<ans<<endl;
46 
47     }
48 
49     return 0;
50 }

View Code

14.HDU 2577 How to Type

题意：给出一串字符串（只有大小写字母），问在keyboard上打出最少需要多少个按钮。

2个数组，

on[i] 表示打完第i个字母后CapsLock开着

off[i] 表示打完第i个字母后CapsLock关着

初始化：

on[i]=1

off[i]=0

注意最后 on[len]++

因为最后还要把CapsLock关了

 1 #include<iostream>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<cctype>
 5 using namespace std;
 6 
 7 const int maxn=105;
 8 
 9 int off[maxn];
10 
11 int on[maxn];
12 
13 int main()
14 {
15     int test;
16 
17     cin>>test;
18 
19     while(test--)
20     {
21         char str[maxn];
22 
23         cin>>str;
24 
25         int len=strlen(str);
26 
27         off[0]=0;
28         on[0]=1;
29 
30         for(int i=1;i<=len;i++)
31         {
32             if(islower(str[i-1]))
33             {
34                 on[i]=min(off[i-1]+2,on[i-1]+2);
35 
36                 off[i]=min(off[i-1]+1,on[i-1]+2);
37             }
38             else{
39 
40                 on[i]=min(off[i-1]+2,on[i-1]+1);
41 
42                 off[i]=min(off[i-1]+2,on[i-1]+2);
43             }
44         }
45 
46         on[len]++;
47 
48         int ans=off[len]<on[len]?off[len]:on[len];
49 
50         cout<<ans<<endl;
51 
52     }
53 
54     return 0;
55 
56 }

View Code

15. HDU 1159 Common Subsequence

题意：给出2个字符串

求出这2个字符串的最长公共子序列 LCS

dp[i][j]表示在比较s的第i个字符和t的第j个字符后的最大值

考虑2个字符相同和不同的情况

dp的下标从1开始的话可以省去很多的初始化

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstring>
 4 
 5 using namespace std;
 6 
 7 const int maxn=500;
 8 
 9 int dp[maxn][maxn];
10 
11 char s[maxn];
12 char t[maxn];
13 
14 int main()
15 {
16     while(cin>>s>>t)
17     {
18         int lenS=strlen(s);
19         int lenT=strlen(t);
20 
21         memset(dp,0,sizeof(dp));
22 
23         for(int i=1;i<=lenS;i++)
24             for(int j=1;j<=lenT;j++)
25             {
26                 if(s[i-1]==t[j-1])
27                     dp[i][j]=dp[i-1][j-1]+1;
28                 else
29                     dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
30             }
31 
32         cout<<dp[lenS][lenT]<<endl;
33 
34     }
35 
36     return 0;
37 }

View Code

16. HDU 1421 搬寝室

题意：现在有n件物品，小明要把其中的2*k件搬去其他宿舍，

　　　小明每次拿2件物品，疲劳值为2件的质量之差的平方

　　　现在问小明搬完这2*k件后，疲劳值最小为多少

思路：先排序，再dp

　　　dp[i][j]=min(dp[i-1][j],dp[i-2][j-1]+(a[i]-a[i-1])*(a[i]-a[i-1]);

　　　注意初始化

 1 #include<iostream>
 2 #include<cstring>
 3 #include<algorithm>
 4 
 5 using namespace std;
 6 
 7 #define LL long long
 8 
 9 const LL inf=100000000;
10 const int maxn=2010;
11 
12 LL dp[maxn][maxn];
13 LL a[maxn];
14 
15 int main()
16 {
17     int n,k;
18     while(cin>>n>>k)
19     {
20         for(int i=1;i<=n;i++)
21             cin>>a[i];
22 
23         sort(a+1,a+n+1);
24 
25        // for(int i=2;i<=n;i++)
26         //    b[i]=(a[i]-a[i-1])*(a[i]-a[i-1]);
27 
28         for(int i=1;i<=n;i++)
29             for(int j=1;j<=k;j++)
30                 dp[i][j]=inf;
31 
32         dp[0][0]=0;
33 
34         for(int i=2;i<=n;i++)
35             //j=k开始不合逻辑
36             for(int j=i/2;j>=1;j--)   
37                 dp[i][j]=min(dp[i-1][j],dp[i-2][j-1]+(a[i]-a[i-1])*(a[i]-a[i-1]));
38 
39         cout<<dp[n][k]<<endl;
40     }
41 
42     return 0;
43 }

View Code

17. HDU 1864 最大报销额

题意：给你n张发票，和最大的报销额为sum，

　　　每张发票有m件物品，满足一定条件的发票就可以报销，

　　　现在问你这些发票的最大报销额是多少

　　　01背包

　　　对每一张发票进行判断，若可以报销则把这张发票的总额加入到数组money[tot++]

　　　tot--

　　　然后把tot这么多张发票作为物品

　　　同时把tot作为背包容量

　　　dp后，找出满足dp[i]<=sum中的dp[i]的最大值

 1 #include<iostream>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<cstdio>
 5 using namespace std;
 6 
 7 const int maxn=33;
 8 
 9 double dp[30010];
10 double money[maxn];
11 
12 int main()
13 {
14 
15     double sum;
16     int n;
17 
18     while(cin>>sum>>n)
19     {
20         if(!n)
21             break;
22 
23         int tot=1;
24 
25         for(int j=1;j<=n;j++)
26         {
27             int m;
28             double a=0.0,b=0.0,c=0.0;
29             double cnt;
30             char str;
31             char strstr;
32             bool flag=true;
33 
34             cin>>m;
35 
36             for(int i=1;i<=m;i++)
37             {
38                 cin>>str>>strstr>>cnt;
39                 if(str=='A')
40                     a+=cnt;
41                 else if(str=='B')
42                     b+=cnt;
43                 else if(str=='C')
44                     c+=cnt;
45                 else
46                     flag=false;
47             }
48 
49             if(flag&&a<=600.00&&b<=600.00&&c<=600.00&&a+b+c<=1000.00)
50                 money[tot++]=a+b+c;
51         }
52 
53         memset(dp,0,sizeof(dp));
54         tot--;
55 
56         for(int i=1;i<=tot;i++)
57             for(int j=tot;j>0;j--)
58                 dp[j]=max(dp[j],dp[j-1]+money[i]);
59 
60         double ans=0;
61         for(int i=1;i<=tot;i++)
62             if(dp[i]<=sum&&dp[i]>ans)
63                 ans=dp[i];
64 
65         printf("%.2f
",ans);
66     }
67     return 0;
68 }

View Code

18.