?
又是一道关于概率的题目，考虑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 ************************/