题解 | #最大报销额#

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Map;
import java.util.Scanner;

class Item{
    double price;
    String type;

    public static final HashSet<String> invoiceItem=new HashSet<>();
    static {
        invoiceItem.add("A");
        invoiceItem.add("B");
        invoiceItem.add("C");
    }

    public static Item stringToItem(String str)
    {
        String[] split = str.split(":");
        return new Item(Double.parseDouble(split[1]),split[0]);
    }

    public Item(double price, String type) {
        this.price = price;
        this.type = type;
    }

    public Item() {
    }
}
class Invoice {
    int n;
    Item[] items;
    double sumPrice=0;


    boolean isVail;

    public boolean isVail() {
        return isVail;
    }

    public static Invoice stringToInvoice(String invoice)
    {
        String[] s = invoice.split(" ");
        int n = Integer.parseInt(s[0]);
        Item[] ans = new Item[n];
        double sumPrice=0;
        boolean flag=true;
        for (int i = 1; i <= n; i++) {
            Item item = Item.stringToItem(s[i]);
            sumPrice+=item.price;
            if (item.price>600 || !Item.invoiceItem.contains(item.type))
                flag=false;
            ans[i-1]= item;
        }

        return new Invoice(n,ans,sumPrice,flag && sumPrice<=1000);
    }

    public Invoice(int n, Item[] items, double sumPrice, boolean isVail) {
        this.n = n;
        this.items = items;
        this.sumPrice = sumPrice;
        this.isVail = isVail;
    }

    public Invoice() {
    }


}
class Solution{
    double minLastPrice=Integer.MAX_VALUE;

    public double getMaxPrice(Invoice[] invoices,double maxPrice)
    {
        dfs(0,invoices,maxPrice);
        return maxPrice-minLastPrice;
    }

    void dfs(int i,Invoice[] invoices,double lastPrice)
    {
        if (i>=invoices.length)
        {
            minLastPrice= Math.min(minLastPrice,lastPrice);
            return;
        }

        dfs(i+1,invoices,lastPrice);
        if (lastPrice>=invoices[i].sumPrice && invoices[i].isVail())
        {
            dfs(i+1,invoices,lastPrice-invoices[i].sumPrice);
        }
    }

}
public class Main {
    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNextLine())
        {
            double price = scanner.nextDouble();
            int n = scanner.nextInt();
            if (n==0)
                break;
            Invoice[] invoices = new Invoice[n];
            for (int i = 0; i < n;) {
                String s = scanner.nextLine();
                if (s.length()!=0)
                    invoices[i++]=Invoice.stringToInvoice(s);
            }

            System.out.printf("%.2f\n",new Solution().getMaxPrice(invoices, price));
        }
    }
}