程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> 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;
}

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved