题解 | #最大报销额#

#include <bits/stdc++.h>
#include <string>
#include <vector>
using namespace std;
/*可以考虑将所有金额乘以100倍*/
int limit;//报销额度
double temp_limit;
int receipt_num;//发票数目
int num;
struct receipt {
    //ABC类花费
    int cost_A;
    int cost_B;
    int cost_C;
    int cost;
};
vector<receipt> v;
string s;
receipt one;//一张发票
int main() {
    while (cin >> temp_limit) {
        limit=(temp_limit*100);//报销额度乘以100
        v.clear();
        cin >> receipt_num; //发票张数
        if (receipt_num == 0) continue; //需要报销的发票数目为0
        while (receipt_num--) {
            one.cost_A = one.cost_B = one.cost_C = 0;
            cin >> num; //这张发票上所开物品的件数
            bool isinvalid=0;//默认合法
            while (num--) {
                cin >> s;
                if (s[0] == 'A') one.cost_A += stod(s.substr(2))*100; //将字符串转化为double
                else if (s[0] == 'B') one.cost_B += stod(s.substr(2))*100;
                else if (s[0] == 'C') one.cost_C += stod(s.substr(2))*100;
                else
                {
                    isinvalid=1;
                }
            }
            //如果不是ABC类，应该作废
            if(isinvalid==1) continue;
            //要求每张发票的总额不得超过1000元，每张发票上，单项物品的价值不得超过600元
            if (max(one.cost_A, max(one.cost_B, one.cost_C)) > 60000 ||
                    one.cost_A + one.cost_B + one.cost_C > 100000)    continue;
            else {
                one.cost = one.cost_A + one.cost_B + one.cost_C;
                v.push_back(one);//将这个发票保存
            }
        }
        //以上是处理输入
        vector<int> dp(limit+1,0);//dp[i]代表i元钱最多能报销的发票总额是多少
        for(int i=0;i<v.size();i++)
        {
            for(int j=limit;j>=1;j--)
            {
                if(j-v[i].cost>=0)
                   dp[j]=max(dp[j],dp[j-v[i].cost]+v[i].cost);
            }
        }
        //处理输出
        cout<<fixed<<setprecision(2)<<double(dp[limit])/100<<endl;
    }
}
// 64 位输出请用 printf("%lld")