SRM 628 D1L3：DoraemonPuzzleGame，math，后市展望，dp

称号：http://community.topcoder.com/stat?c=problem_statement&pm=13283&rd=16009

參考：http://apps.topcoder.com/wiki/display/tc/SRM+628

開始不知道怎么求期望。普通方法 p1*c1 + p2 *c2 + ... 行不通，看了Editoral才发现原来能够用dp的方法求期望，基本思想是令函数 f(t, r)为剩余 t 个 levels 还须要的花费的时间。r为一定须要获得2个stars的levels数量，则有：

当 t != r 时，须要获得one or two stars, f(t, r) = 1 + p0 * f(t, r) + p1 * f(t-1, r) + p2 * f(t-1, r-1). 解得 f(t, r) = ( 1 + p1 * f(t-1, r) + p2 * f(t-1, r-1) ) / (1 - p0).

当 t == r时，必须获得two stars, f(t, r) = 1 + (1 - p2) * f(t, r) + p2 * f(t-1, r-1). 解得 f(t, r) = ( 1 + p2 * f(t-1, r-1) ) / p2.

处理的顺序为按p2非递减就可以。

代码：

#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <iostream>
#include <sstream>
#include <iomanip>

#include <bitset>
#include <string>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <set>
#include <map>

#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cmath>
#include <cstring>
#include <ctime>
#include <climits>
using namespace std;

#define CHECKTIME() printf("%.2lf
", (double)clock() / CLOCKS_PER_SEC)
typedef pair<int, int> pii;
typedef long long llong;
typedef pair<llong, llong> pll;
#define mkp make_pair

/*************** Program Begin **********************/
const int MAX_N = 2001;
double dp[MAX_N][MAX_N];
class DoraemonPuzzleGame {
public:
	int N;
	vector <pair<double, double>> prob;
	double rec(int t, int r)
	{
		double & res = dp[t][r];
		// base case
		if (0 == t) {
			res = 0;
			return res;
		}
		if (res > -0.5) {
			return res;
		}
		res = 0.0;
		double p1 = prob[N - t].second;
		double p2 = prob[N - t].first;
		if (t != r) {	// get one or two stars int this level
			res = (1 + p1 * rec(t-1, r) + p2 * rec(t-1, max(0, r-1))) / (p1 + p2);
		} else {	// must get two stars
			res = (1 + p2 * rec(t-1, max(0, r-1))) / p2;
		}
		return res;
	}
	double solve(vector <int> X, vector <int> Y, int m) {
		N = X.size();
		for (int i = 0; i < MAX_N; i++) {
			for (int j = 0; j < MAX_N; j++) {
				dp[i][j] = -1.0;
			}
		}

		for (int i = 0; i < X.size(); i++) {
			prob.push_back(mkp(Y[i] / 1000.0, X[i] / 1000.0));
		}
		sort(prob.begin(), prob.end());
		
		return rec(N, m - N);
	}

};

/************** Program End ************************/