SRM515-550-Correct.cpp

SRM515-550-Correct.cpp

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

typedef long long int int64;
typedef vector<int> VI;
#define REP(i,a,b) for (int i=int(a); i<int(b); ++i)

class NewItemShop {
public:
	double getMaximum(int, vector <string>);
};

int W[24];
double C[24];
double P[24];
int last[24];

typedef pair<int, int> COND;
typedef map<COND, double> DPT;
DPT dp;

double rec(int bitmask, int h, int s) {
	if (h>=24) return 0;
	if (s<=0) return 0;
	
	if ( (h>0) && (last[W[h-1]]==h-1) )
		bitmask |= (1<<(W[h-1]));
	
	COND cond = COND(bitmask, h*25+s);
	DPT::iterator dit = dp.find(cond);
	if (dit!=dp.end()) return dit->second;

	double v = 0;
	if (W[h]==-1||(bitmask&(1<<W[h]))) {
		v = rec(bitmask, h+1, s);
	} else {
		// Customer didn't come
		double nocome = rec(bitmask, h+1, s);
		
		// Customer comes
		int newmask = bitmask|(1<<W[h]);
		double yes = C[h] + rec(newmask, h+1, s-1);
		double no = rec(newmask, h+1, s);
		
		v = (1.0-P[h]) * nocome;
		v += P[h] * max(yes, no);
		
		// cout<<C[h]<<endl;
	}
	// printf("%d %d %d: %lf\n", h, s, bitmask, v);
	dp[cond] = v;
	return v;
}

double NewItemShop::getMaximum(int swords, vector <string> customers) {
	REP(i, 0, 24) {
		W[i] = -1;
		last[i] = -1;
	}
	REP(i, 0, customers.size()) {
		const char* pc = customers[i].c_str();
		int t, c, p;
		int totalp = 100;
		while(sscanf(pc, "%d,%d,%d", &t, &c, &p)!=-1) {
			do { ++pc; } while (*pc!=' ' && *pc!=0);
			W[t] = i;
			C[t] = c;
			P[t] = double(p) / double(totalp);
			totalp -= p;
			last[i] = t;
			// cout<<W[t]<<" "<<C[t]<<" "<<P[t]<<endl;
		}
	}
	dp.clear();
	return rec(0, 0, swords);
}

//Powered by [KawigiEdit] 2.0!