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

称号：

c=problem_statement&pm=13283&rd=16009">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\n", (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 ************************/