最大报销额-dp.txt

来自「浙江大学研究生复试上机题目及解答。欢迎大家下载。」· 文本 代码 · 共 62 行

#include <cstdio>
#include <string>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
const int NMAX = 30 +10;
const int TMAX = 1000*30*100 +1000;
double q;
int n,m,nq;
double item[3];
char type;
double price,sum;
bool cal[2][TMAX];
int nn,w[NMAX];
int cal_max() {
    int i,j;
    bool * now,* next;
    now = cal[0]; next = cal[1];
    memset(cal,false,sizeof(cal));
    now[0] = true;
    nq = 100*q;
    for (i=0;i<nn;i++) {
        for (j=0;j<=nq;j++) {
            if (now[j]) {
                next[j] = true;
                if (j+w[i] <= nq) next[ j+w[i] ] = true;
            }
        }
        swap(now,next);
    }
    for (i=nq;i>=1;i--) {
        if (now[i]) return i;
    }
}
int main() {
    int i,j;
    char tmp[100];
    while (scanf("%lf %d",&q,&n),n) {
        nn = 0;
        for (i=0;i<n;i++) {
            for (j=0;j<3;j++) item[j] = 0;
            scanf("%d",&m);
            sum = 0;
            for (j=0;j<m;j++) {
                scanf("%s",tmp);
                sscanf(tmp,"%c:%lf",&type,&price);
                if (!(type>='A' && type<='C')) {
                    sum = 9999.0;
                    break;
                }
                item[type-'A'] += price;
            }
            for (j=0;j<3;j++) {
                if (item[j] <= 600.0) sum += item[j];
                else sum = 9999.0;
            }
            if (sum <= 1000.0) w[nn ++] = int(sum*100);
        }
        printf("%.2lf\n",cal_max()/100.0);
    }
}