题解 | #最大报销额#

#include <iostream>
#include <queue>
using namespace std;
priority_queue<double> heap;
double ans;
//深搜回溯求最大和
//直接贪心取值无法ac，浮点数没法dp
//把money都乘以100,小数点后两位映射到整数,就可以背包
void dfs(double sum, double q)
{
    if(sum > q) return;
    else ans = max(ans, sum);
    if(heap.empty()) return;
    double tmp = heap.top();
    heap.pop();
    //当前堆顶是否加入sum中进行深搜
    dfs(sum, q), dfs(sum + tmp, q);
    heap.push(tmp);
}
bool valid(char a, double p)
{
    if(a == 'A' || a == 'B' || a == 'C') return p <= 600.00;
    return false;
}
int main() {
    double q; 
    int n, m;
    bool flag;
    while (cin >> q >> n && n) { // 注意 while 处理多个 case
        heap = priority_queue<double>();
        while(n --)
        { 
            flag = true;
            cin >> m;
            double sum = 0.0;
            while(m --)
            {
                char a, b;
                double p;
                cin >> a >> b >> p;
                flag &= valid(a, p);
                sum += p;
            }
            if(flag && sum <= 1000 && sum <= q) 
            {
                heap.push(sum);
                // cout <<"valid : " <<sum << endl;
            }
        }
        ans = 0;
        dfs(0.0, q);
        printf("%.2lf\n", ans);
    }
}
// 64 位输出请用 printf("%lld")