首页 > 代码库 > hdu--4800--dp

hdu--4800--dp

2024-08-05 14:23:01   218人阅读

一共就2种状态的转移

当我们将状态从x转移到Y的时候 可以选择 换队员 或者不换队员 但是有一点要注意 如果要换队员只能是最新的 也就是刚结束的比赛

而且 不管换不换 比赛场次总是增加了一场 我们总是从(x-1)---->x  这也是符合逻辑的 一定要先进行第(x-1)场的比赛 才能进行第x场的比赛

dp[x,y]表示当前进行到第x场比赛的时候 我是以y为编号在进行<注意 因为这边要求比赛一定要按照顺序打完 所以也就是说打完第n场 就是所有的比赛都打完了>

dp[x][y] = max( dp[x][y] , dp[x-1][y]*p[y][ team[x] ); //不更换

dp[x][y] = max( dp[x][ team[x] ] , dp[x-1][y]*p[y][ team[x] ] );//更换

 1 #include <iostream> 2 #include <algorithm> 3 using namespace std; 4  5 int n , m; 6 const int size = 300; 7 double dp[10010][size]; 8 double p[size][size]; 9 int team[10010];10 11 void solve( )12 {13     for( int i = 0 ; i<=m ; i++ )14         dp[0][i] = 1.0;15     for( int i = 1 ; i<=n ; i++ )16     {17         for( int j = 0 ; j<m ; j++ )18         {19             dp[i][j] = max( dp[i][j] , dp[i-1][j]*p[j][ team[i] ]);20             dp[i][ team[i] ] = max( dp[i][ team[i] ] , dp[i-1][j]*p[j][ team[i] ] );21         }22     }23 }24 25 int main()26 {27     double ans;28     while( ~scanf("%d",&m) )29     {30         m = m * (m-1) * (m-2) / 6;31         for( int i = 0 ; i<m ; i++ )32         {33             for( int j = 0 ; j<m ; j++ )34             {35                 scanf("%lf",&p[i][j]);36             }37         }38         scanf("%d",&n);39         for( int i = 1 ; i<=n ; i++ )40         {41             scanf("%d",&team[i]);42         }43         memset( dp , 0 , sizeof(dp) );44         solve( );45         ans = 0;46         for( int i = 0 ; i<m ; i++ )47         {48             ans = max( ans , dp[n][i] );49         }50         printf("%.6lf\n",ans);51     }52     return 0;53 }
View Code

 

today:

　　糟糕透了

　　ffffffffk

　　

hdu--4800--dp


联系
我们