Note: This article is available in Chinese only. 本文暂无英文版本。
View original
题意：中文题目，不多说了。
思路：正解是01背包，呵呵呵。
出题人是傻逼吗？
不给数据范围？
以及，正解的01背包基于所有的发票额度的只有2位小数。这是让人猜？
本来看到这题这么恶心时不打算写的…
写了的原因纯粹是为了吐槽傻逼出题人..
简直是我做得最垃圾的题目之一。
1/* ***********************************************
2Author :111qqz
3Created Time :2016年11月16日 星期三 14时13分28秒
4File Name :code/hdu/1864.cpp
5 ************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,int >
26#define MP make_pair
27
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33const int N=3E6+7;
34double P;
35int n;
36int dp[N], value[35];
37
38void solve( int value,int cost )
39{
40 for ( int i = int(P) ; i >= cost ; i--)
41 dp[i] = max(dp[i],dp[i-cost]+value);
42}
43int main()
44{
45#ifndef ONLINE_JUDGE
46 freopen("code/in.txt","r",stdin);
47#endif
48
49 while (~scanf("%lf%d",&P,&n)){
50// puts("miao?");
51 if (n==0) break;
52 P*=100;
53 ms(dp,0);
54 int cnt = 0 ;
55 for ( int i = 1 ; i <= n ; i++){
56 int m;
57 scanf("%d",&m);
58 double tmp;
59 double sum = 0 ;
60 double sa=0,sb=0,sc=0;
61 char no;
62 bool die = false;
63 while (m--){
64 scanf(" %c:%lf",&no,&tmp);
65 if (no=='A'&&sa+tmp<=600) sa += tmp;
66 else if (no=='B'&&sb+tmp<=600) sb += tmp;
67 else if (no=='C'&&sc+tmp<=600) sc += tmp;
68 else die = true;
69 sum = sum + tmp;
70 if (sum>1000) die = true;
71 }
72 sum*=100;
73 if (!die) value[++cnt] = sum;
74 }
75
76 for ( int i = 1 ; i <= cnt ; i++) solve(value[i],value[i]);
77 int ans = 0 ;
78 for ( int i = 1 ; i <= P ; i++) ans = max(ans,dp[i]);
79 printf("%.2lf\n",ans*1.0/100);
80 }
81
82#ifndef ONLINE_JUDGE
83 fclose(stdin);
84#endif
85 return 0;
86}