概率dp

通过考试（京东2017实习生真题） 概率dp，定义状态前i个题目对j个的概率，递推求解 #include<cstdio> #include <iomanip> #include<iostream> using namespace std; int n, m; int p[101]; double dp[101][101],tmp; int main() { freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); cin >> n; m = (n * 3 + 4) / 5; for (int i = 1; i<=n; i++) { cin >> p[i]; } /*for (int i = 0; i <= n; i++) { dp[i][0] = 1; }*/ dp[0][0] = 1; for (int i = 1; i <= n; i++) { dp[i][0] = dp[i - 1][0] * (100.0 - p[i]) / 100; for (int j = 1; j <= i; j++) { dp[i][j] = dp[i - 1][j] * (100.0 - p[i]) / 100 + dp[i - 1][j - 1] * 1.0*p[i] / 100; } } tmp = 0; for (int i = m; i <= n; i++) { tmp += dp[n][i]; } cout.setf(ios::fixed); cout <<setprecision(5)<<tmp<< endl; fclose(stdin); fclose(stdout); }