程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> POJ 2151 Check the difficulty of problems（概率DP）

POJ 2151 Check the difficulty of problems（概率DP）

編輯：C++入門知識

POJ 2151 Check the difficulty of problems（概率DP）

題意：ACM比賽中，有T個隊， m道題，每個隊能解出每道題的概率已知，求每個隊至少解出一道題並且冠軍隊解出至少n道題的概率。

思路：首先，我們不難想到用d[i][j]表示前i個隊，冠軍隊解出了j道題的概率。那麼答案就是sum(a[n][j]) j >= n 。每次轉移的代價是，決策第i個隊解決了多少道題，並且更新j（冠軍隊的解題數）。那麼難點就在於怎麼求出第i個隊解出j個題的概率。我們再求一次DP，用x[i][j][k]表示，第i個隊在前j個題中解出了k個題的概率。那麼轉移就是x[i][j][k] = x[i][j-1][k-1] * a[i][j] + x[i][j-1][k] * a[i][j]。邊界條件是：

1. x[0][0][0] = 1，表示前0個隊解出0題，這是顯然的。

2. 還有一個就是x[i][j][0] = (1-a[i][1]) * (1-a[i][2]) * ...... * (1 - a[i][j])。

細節參見代碼：

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
using namespace std;
typedef long long ll;
typedef long double ld;
const ld eps = 1e-9, PI = 3.1415926535897932384626433832795;
const int mod = 1000000000 + 7;
const int INF = 0x3f3f3f3f;
const int seed = 131;
const ll INF64 = ll(1e18);
const int maxn = 1000 + 10;
int T,n,m,vis[maxn][33],kase = 0;
double a[maxn][33],x[maxn][33][33], d[maxn][33];
double dp(int i, int j) {
    double& ans = d[i][j];
    if(i == T + 1) return j >= n ;
    if(vis[i][j] == kase) return ans;
    vis[i][j] = kase;
    ans = 0;
    bool ok = false;
    for(int k = 1; k <= m; k++) {
        ans += dp(i+1, max(j, k)) * x[i][m][k];
    }
    return ans;
}
int main() {
    while(~scanf("%d%d%d",&m,&T,&n) && (m || T || n)) {
        for(int i=1;i<=T;i++) {
            for(int j=1;j<=m;j++) scanf("%lf",&a[i][j]);
        }
        memset(x, 0, sizeof(x));
        ++kase;
        for(int i=1;i<=T;i++) {
            x[i][0][0] = 1;
            for(int j=1;j<=m;j++) {
                x[i][j][0] = x[i][j-1][0] * (1 - a[i][j]);
            }
            for(int j=1;j<=m;j++) {
                for(int k=1;k<=j;k++) {
                    x[i][j][k] = x[i][j-1][k-1] * a[i][j];
                    if(j-1 >= k) x[i][j][k] += x[i][j-1][k] * (1 - a[i][j]);
                }
            }
        }
        double ans = dp(1, 0);
        printf("%.3f\n",ans);
    }
    return 0;
}