程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> Gym 100338I TV show （dfs枚舉）

Gym 100338I TV show （dfs枚舉）

編輯：C++入門知識

Gym 100338I TV show （dfs枚舉）

Gym 100338I

題意：

一個人去參加電視有獎問答的節目，初始獎金為100元，每答對一道問題獎金翻倍，答錯獎金清零。此外有一次保險機會：花費C的獎金，下一題可以答對獎金翻倍，答錯獎金不清零。
現在給你答對每道題的概率，求最優答題策略的獎金期望。

思路：

先不考慮有保險機會。回答對第j題後離開的獎金期望就是：
100?2j?∏ji=1pi
那麼我們枚舉回答對第j題後離開的獎金期望，維護其最大值即可（注意也可以一題不回答直接走人，期望為100）。

那麼我們現在來考慮有保險機會的情況，我們枚舉回答第j題前用保險，那麼就會分裂出兩種情況，第j題答沒答對，比如說，答j題前有200元，c = 50 , pj = 50 ，那麼就分裂出答對後300元，沒答對150元，然後把300元與150元分別當做初始獎金，按照之前說的計算方式計算後加起來即是第j題前用保險的期望，維護最大值就是答案。

代碼：

/*
* @author FreeWifi_novicer
* language : C++/C
*/
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include

using namespace std;

#define clr( x , y ) memset(x,y,sizeof(x))
#define cls( x ) memset(x,0,sizeof(x))
#define mp make_pair
#define pb push_back
typedef long long lint;
typedef long long ll;
typedef long long LL;

double a[55] ;

int n , c ; 
double dfs( int cur , double e , bool have ){
    if( cur >= n )
        return e ;
    double tmp = max( e , a[cur] * dfs( cur + 1 , 2 * e , have ) ) ;
    double money = 0 ;
    if( e > c && have ){
        money += ( 1.0 - a[cur] ) * dfs( cur + 1 , e - c , false ) ;
        money += ( a[cur] ) * dfs( cur + 1 , 2 * ( e - c ) , false ) ;
    }
    tmp = max( tmp , money ) ;
    return tmp ;
}

int main(){
  freopen("tvshow.in","r",stdin);
  freopen("tvshow.out","w",stdout);
    //freopen( "input.txt" , "r" , stdin ) ;
    while( cin >> n >> c ){
        for( int i = 0 ; i < n ; i++ ){
           scanf( "%lf" , a+i ) ; 
           a[i] /= 100 ;
        }
        double ans = dfs( 0 , 100.0 , true ) ;
        printf( "%.12f\n" , ans ) ;
    }
    return 0;
}