程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> codeforces 167B Wizards and Huge Prize 概率dp

codeforces 167B Wizards and Huge Prize 概率dp

編輯：關於C++

題意：給定n個對手，至少要擊敗其中 l 個人，現在有口袋容量為 k下面n個數字表示擊敗這個人的概率

下面n個數字（若為-1表示擊敗這個人可以獲得一個金幣，若>0則表示可以增加口袋容量為這個數字）

求：至少擊敗其中的l個人，且獲得的總口袋容量 >= 獲得的金幣個數的概率是多少。（即任何時候金幣都不能放不下）

思路：設dp[i][j][k]表示當前前i個人已經戰勝j個人，且剩余口袋容量為k的概率，簡單的推下公式即可。有一點需要主要，可能一開始

剩余口袋容量<0後來大於0，所以要加一個常數不讓它為負，只要最後剩余容量>=0即可。詳見代碼：

/*********************************************************
  file name: codeforces167B.cpp
  author : kereo
  create time:  2015年02月01日 星期日 21時34分15秒
*********************************************************/
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
const int sigma_size=26;
const int N=200+50;
const int MAXN=100000+50;
const int inf=0x3fffffff;
const double eps=1e-8;
const int mod=100000000+7;
#define L(x) (x<<1)
#define R(x) (x<<1|1)
#define PII pair
#define mk(x,y) make_pair((x),(y))
int n,m,k;
int a[N];
double p[N],dp[N][N][2*N+10];
int main(){
    while(~scanf("%d%d%d",&n,&m,&k)){
        memset(dp,0,sizeof(dp));
        dp[0][0][N+k]=1.0;
        for(int i=1;i<=n;i++){
            scanf("%lf",&p[i]);
            p[i]/=100;
        }
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        for(int i=1;i<=n;i++){
            for(int j=0;j