zoj3010.cpp

来自「最近在acm.zju.edu.cn上通过的题目的代码」· C++ 代码 · 共 45 行

#include <algorithm>
using namespace std;

int n;
double m;
int g[20];
double c[20];
double f[1024];

double search(int state){
	if (f[state] >= 0) return f[state];
    int tst;  double tmp;
    f[state] = 0;
    for (int i = 0; i < n; i++){
    	tst = state ^ g[i];
        tmp = search(tst);
        if (tmp > 0) {
        	tmp *= c[i];
        	if (tmp > f[state]) f[state] = tmp;
        }
	}
    return f[state];
}


int main(){
	while ((scanf("%d%lf", &n, &m) != EOF && n + m)){
		for (int i = 0; i < n; i++){
        	g[i] = 1 << i;
            int t, x; scanf("%d", &t);
            for (int j = 0; j < t; j++){
            	scanf("%d", &x); x--;
            	g[i] ^= (1 << x);
            }
            scanf("%lf", &c[i]);
            c[i] /= 100.0; c[i] = 1 - c[i];
        }
        for (int i = 0; i < (1 << n); i++) f[i] = -1;
        f[(1 << n) - 1] = m;
        search(0);          
        if (f[0] <= 0) puts("-1"); else printf("%.2lf\n", f[0]);
	}
	return 0;
}