首页 > 代码库 > hdu--4800--dp
hdu--4800--dp
一共就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 }
today:
糟糕透了
ffffffffk
hdu--4800--dp
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。