最大报销额-dfs.txt

浙江大学研究生复试上机题目及解答。欢迎大家下载。

#include <cstdio>
#include <string>
using namespace std;
double max1,val[26],sum,has[35],max2;
int n,num;
void dfs(double sum,int p) {
    if(sum>max1)return;
    if(p<0) {
        if(sum>max2)max2=sum;
        return;
    }
    if(sum>max2)max2=sum;
    dfs(sum,p-1);
    dfs(sum+has[p],p-1);
}
int main() {
    int i,j,m;
    double s;
    char p,f;
    while(scanf("%lf%d",&max1,&n)&&n) {
        num=0;
        for(i=0;i<n;i++) {
            sum=0;
            memset(val,0,sizeof(val));
            scanf("%d",&m);
            f=0;
            for(j=0;j<m;j++) {
                scanf(" %c:%lf",&p,&s);
                val[p-'A']+=s;
                if(p!='A'&&p!='B'&&p!='C')f=1;
                sum+=s;
                if(sum>max1||sum>1000.0||val[p-'A']>600.0)f=1;
            }
            if(f)continue;
            has[num++]=sum;
        }
        s=0;
        for(i=0;i<num;i++)s+=has[i];
        if(s<=max1)max2=s;
        else {
            max2=0;
            dfs(0,num-1);
        }
        printf("%.2lf\n",max2);
    }
    return 0;
}