程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> SRM 620 D2L3: RandomGraph, dp

SRM 620 D2L3: RandomGraph, dp

編輯：C++入門知識

又是一道關於概率的題目，考慮dp方法，關鍵是找准突破口，將題目條件的“至少有一個大於4的連通圖”轉換為“所有連通圖都小於等於3”。

代碼：

#include 
#include 
#include 
#include 
#include 
#include 
#include 

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include

#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

#define CHECKTIME() printf(%.2lf
, (double)clock() / CLOCKS_PER_SEC)
typedef pair pii;
typedef long long llong;
typedef pair 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 ************************/