DP ZOJ 3735 Josephina and RPG-白红宇

DP ZOJ 3735 Josephina and RPG

阅读量：6632 次

发布时间：2019-06-25

本文共 1968 字，大约阅读时间需要 6 分钟。

题意：告诉你C(m,3)个队伍相互之间的胜率，然后要你依次对战n个AI队伍，首先任选一种队伍，然后战胜一个AI后可以选择替换成AI的队伍，也可以不换，问你最后最大的胜率是多少。

分析：dp[i][j][0/1] 表示第i个AI，用j的id去攻打，此j可以是上一个状态交换AI的id而来也可以不是，状态转移方程：

dp[i][j][0] = max (dp[i-1][j][0], dp[i-1][j][1]) * p[j][a[i]];

if (i > 1)

dp[i][a[i-1]][1] = max (dp[i][a[i-1]][1], max (dp[i-1][j][0], dp[i-1][j][1]) * p[a[i-1]][a[i]]);

效率并不是很高。。。

/************************************************* Author        :Running_Time* Created Time  :2015/10/24 星期六 13:32:44* File Name     :J.cpp ************************************************/#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 #include 
                  
                   #include 
                   
                    #include 
                    
                     #include 
                     
                      using namespace std;#define lson l, mid, rt << 1#define rson mid + 1, r, rt << 1 | 1typedef long long ll;const int N = 1e4 + 10;const int INF = 0x3f3f3f3f;const int MOD = 1e9 + 7;const double EPS = 1e-8;double dp[N][122][2];double p[122][122];int a[N];int main(void) { int m, r, n; while (scanf ("%d", &m) == 1) { if (m == 3) r = 1; else if (m == 4) r = 4; else if (m == 5) r = 10; else if (m == 6) r = 20; else if (m == 7) r = 35; else if (m == 8) r = 56; else if (m == 9) r = 84; else if (m == 10) r = 120; for (int i=1; i<=r; ++i) { for (int j=1; j<=r; ++j) { scanf ("%lf", &p[i][j]); } } scanf ("%d", &n); for (int i=1; i<=n; ++i) { scanf ("%d", &a[i]); a[i]++; } memset (dp, 0, sizeof (dp)); for (int i=1; i<=r; ++i) dp[0][i][0] = dp[0][i][1] = 1; for (int i=1; i<=n; ++i) { for (int j=1; j<=r; ++j) { dp[i][j][0] = max (dp[i-1][j][0], dp[i-1][j][1]) * p[j][a[i]]; if (i > 1) dp[i][a[i-1]][1] = max (dp[i][a[i-1]][1], max (dp[i-1][j][0], dp[i-1][j][1]) * p[a[i-1]][a[i]]); } } double ans = 0; for (int i=1; i<=r; ++i) ans = max (ans, max (dp[n][i][0], dp[n][i][1])); printf ("%.6f\n", ans); } return 0;}

转载于:https://www.cnblogs.com/Running-Time/p/4907405.html

你可能感兴趣的文章