Gym 100338I题意：
一个人去参加电视有奖问答的节目，初始奖金为100元，每答对一道问题奖金翻倍，，答错奖金清零。此外有一次保险机会：花费C的奖金，下一题可以答对奖金翻倍，答错奖金不清零。 现在给你答对每道题的概率，求最优答题策略的奖金期望。
思路：
先不考虑有保险机会。回答对第j题后离开的奖金期望就是： 那么我们枚举回答对第j题后离开的奖金期望，维护其最大值即可（注意也可以一题不回答直接走人，期望为100）。
那么我们现在来考虑有保险机会的情况，我们枚举回答第j题前用保险，那么就会分裂出两种情况，第j题答没答对，比如说，答j题前有200元，c = 50 , pj = 50 ，那么就分裂出答对后300元，没答对150元，然后把300元与150元分别当做初始奖金，按照之前说的计算方式计算后加起来即是第j题前用保险的期望，维护最大值就是答案。
代码：/** @author FreeWifi_novicer* language : C++/C*/;lint;ll;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;}
一路走来，我们无法猜测将是迎接什么样的风景，
