题意：现有一笔经费可以报销一定额度的发票。允许报销的发票类型包括买图书（A类）、文具（B类）、差旅（C类），要求每张发票的总额不得超过1000元，每张发票上，单类物品的价值不得超过600元。现请你编写程序，在给出的一堆发票中找出可以报销的、不超过给定额度的最大报销额。
题解：处理出可以报销的发票的数组 a[] 。
定义：dp[i] 为报销第 i 个发票的情况下报销的最大值；
状态转移：dp[i] = max( dp[i], dp[0 ~ i-1] + a[i]);
#include <bits/stdc++.h>
using namespace std; const double EPS = 1e-;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + ;
const int maxn = + ;
double Q;
int n, m;
double a[maxn];
double dp[maxn]; int main()
{
while(scanf("%lf%d", &Q, &n) != EOF && n){ memset(a, , sizeof(a));
memset(dp, , sizeof(dp)); int cnt = ;
for(int i = ; i < n; i++){
scanf("%d", &m);
bool ok = true;
char kind; double A = , B = , C = , p;
for(int i = ; i < m; i++){
scanf(" %c:%lf", &kind, &p);
if(kind < 'A' || kind > 'C' || p > ) ok = false;
else if(kind == 'A') A += p;
else if(kind == 'B') B += p;
else if(kind == 'C') C += p;
}
if(A > || B > || C > || A + B + C > min(1000.0, Q)) ok = false;
if(ok) a[cnt++] = A + B + C;
} for(int i = ; i < cnt; i++){
for(int j = i - ; j >= ; j--){
if(dp[j] + a[i] <= Q){
dp[i] = max(dp[i], dp[j] + a[i]);
}
}
} double ans = ;
for(int i = ; i < cnt; i++) ans = max(ans, dp[i]); printf("%.2f\n", ans);
} return ;
}