学步园

传送门：【HDU】3076 ssworld VS DDD

题目分析：简单的概率DP。。不过要搞清楚转移边界。。。我就因为边界问题一直wa。。

PS：题目数据给的血量是反的！数据错了

代码如下：

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;

#define REP( i , a , b ) for ( int i = a ; i < b ; ++ i )
#define REV( i , a , b ) for ( int i = a ; i >= b ; -- i )
#define FOR( i , a , b ) for ( int i = a ; i <= b ; ++ i )
#define CLR( a , x ) memset ( a , x , sizeof a )
#define CPY( a , x ) memcpy ( a , x , sizeof a )

const int MAXN = 2005 ;
const double eps = 1e-8 ;

int n , m ;
double dp[MAXN][MAXN] ;
double player1[6] , player2[6] ;
double win , tie , lose ;

void solve () {
	tie = win = lose = 0 ;
	REP ( i , 0 , 6 ) scanf ( "%lf" , player1 + i ) ;
	REP ( i , 0 , 6 ) scanf ( "%lf" , player2 + i ) ;
	REP ( i , 0 , 6 ) REP ( j , 0 , 6 ) {
		double tmp = player1[i] * player2[j] ;
		if ( i > j ) win += tmp ;
		else if ( i == j ) tie += tmp ;
		else lose += tmp ;
	}
	FOR ( i , 0 , n + 1 ) dp[i][m + 1] = 0 ;
	FOR ( i , 0 , m + 1 ) dp[n + 1][i] = 0 ;
	dp[n][m] = 1.0 ;
	REV ( i , n , 1 ) REV ( j , m , 0 ) {
		if ( i == n && j == m ) continue ;
		dp[i][j] = win * dp[i][j + 1] ;
		if ( j ) dp[i][j] += lose * dp[i + 1][j];
		dp[i][j] /= ( 1 - tie ) ;
	}
	double ans = 0 ;
	FOR ( i , 1 , n ) ans += dp[i][0] ;
	printf ( "%.6f\n" , ans ) ;
}

int main () {
	while ( ~scanf ( "%d%d" , &m , &n ) ) solve () ;
	return 0 ;
}