SRM 620 D2L3: RandomGraph, dp

称号：http://community.topcoder.com/stat?

c=problem_statement&pm=13143&rd=15853

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

又是一道关于概率的题目，考虑dp方法。关键是找准突破口，将题目条件的“至少有一个大于4的连通图”转换为“全部连通图都小于等于3”。

代码：

#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 **********************/

double dp[51][51][51];

bool solved[51][51][51];

class RandomGraph {

public:

	int n;

	double p;

	double rec(int a, int b, int c)

	{

		double & res = dp[a][b][c];

		if (solved[a][b][c]) {

			return res;

		}

		int r = n - (a + 2 * b + 3 * c);

		// base case

		if (0 == r) {

			res = 1.0;

			solved[a][b][c] = true;

			return res;

		}

		res = 0.0;

		// r != 0

		res += pow(1 - p, a + 2 * b + 3 * c) * rec(a + 1, b, c);

		if (a >= 1) {

			res += pow(1 - p, a + 2 * b + 3 * c - 1) * a * p * rec(a - 1, b + 1, c);

		}

		if (a >= 2) {

			res += pow(1 - p, a + 2 * b + 3 * c - 2) * p * p * a * (a - 1) / 2 * rec(a - 2, b, c + 1);

		}

		if (b >= 1) {

			res += pow(1 - p, a + 2 * b + 3 * c - 1) * p * 2 * b * rec(a, b - 1, c + 1);

			res += pow(1 - p, a + 2 * b + 3 * c - 2) * p * p * b * rec(a, b - 1, c + 1);

		}

		solved[a][b][c] = true;

		return res;

	}

	double probability(int n, int p) {

		double res = 0;

		this->n = n;

		this->p = p / 1000.0;

		memset(solved, 0, sizeof(solved));

		res = 1 - rec(0, 0, 0);

		return res;

	}

};

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