hdu4800_Josephina and RPG（二维状态dp） - c++编程基础

TOP

hdu4800_Josephina and RPG（二维状态dp）

2015-11-21 00:56:47 来源: 作者: 【大中小】浏览:1次

?题解：dp的状态设为,使用角色 j 去通过第 i 关的最大胜率（dp[i][j] ）

从最后一场开始算：
dp[i][j] = rate[j][ AI[i] ] * max( dp[i+1][j] ,dp[i+1][a[i]);

即：使用角色 j 去通过第 i 关的最大胜率 = 使用角色 j 打赢第 i 关AI的胜率 * max（下一关用 j 通关的概率，下一关换用本关AI通过的概率）

设好初值，历遍即可。

#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
         
           #include
          
            #include 
           
             #include
            
              #include
              #include 
              
                #include
               
                 #include
                
                  #include 
                 
                   #include
                  
                    #include
                   
                     using namespace std; #define mem(x,y) memset(x,y,sizeof(x)) inline int lowbit(int x){ return x&(-x);} typedef long long int LL; const int INF = 0x3f3f3f3f ; const long double PI = acos(0.0) * 2.0; const int N = 10000+10; const double eps = 1e-6; double dp[N][200],rate[200][200]; int ai[N]; int Comb(int x , int y); int main() { int n,m; //ios::sync_with_stdio(false);//关闭同步流 while(scanf(%d,&m) == 1) { int r = Comb(m,3); for(int i = 0 ; i < r ; i++) for(int j = 0 ; j < r ; j++) scanf(%lf,&rate[i][j]); scanf(%d,&n); for(int i = 0 ; i < n ; i++) scanf(%d,&ai[i]); mem(dp,0.0); for(int j = 0 ; j < r ; j++) dp[n-1][j] = rate[j][ ai[n-1] ]; for(int i = n-2 ; i >= 0; i--) { for(int j = 0 ; j < r ; j++) { dp[i][j] = max(dp[i][j],rate[j][ ai[i] ] * max( dp[i+1][j],dp[i+1][ ai[i] ] )); } } double res = 0.0; for(int j = 0 ; j < r ; j++) res = max(res,dp[0][j]); printf(%.6lf ,res); } return 0; } int Comb(int x , int y) { int u=1,v=1,len; if(y==0||x==y) return 1; if(y==1) return x; if(x < y ) return 0; if(y > x/2) y = len = x-y; else len = y; while(len--) { u*= x--; v*= y--; } return (int)(u/v); }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：hdoj1051Wooden Sticks	下一篇：经典中的经典Unique Binary Searc..

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: