This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.
ダーツの投げる場所が$2$つあり，短い距離で投げてあたった場合は$2$点，長い距離で投げてあたった場合は$3$点貰える．それぞれ当たる確立は$P1$%, $P2$%である．$N$回投げて，$W$点以上取った時の確立を求めたい．
$$
dp[i][j] := i回投げてj点以上取った時の確立
$$
として動的計画法．短い距離の場合で$dp[i][j]$に遷移するのは，$i-1$回目に投げて$j-2$点だった時に投げてあたった場合と，$i-1$回目に既に$j$点取っていてはずした場合の和である．同様に長い距離の場合で$dp[i][j]$に遷移するのは$i-1$回目に投げて$j-3$点だった時に投げてあたった場合と，$i-1$回目に既に$j$点取っていてはずした場合の和である．この時，$W$点以上の確立も考慮しなければならない．例えば$W+2$点取る確立(以上ではない)は$-2$から遷移がスタートして$W$に来たと考える事ができるので，遷移元が配列外参照となる場合は単純に$1$として考えてあげれば大丈夫．
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define INF 1<<30
#define mp make_pair
using namespace std ;
typedef long long ll ;
typedef pair < int , int > P ;
double dp [ 1005 ][ 3005 ];
class SimplifiedDarts {
public :
double tryToWin ( int W , int N , int P1 , int P2 ) {
double p1 = P1 / ( 100.0 );
double p2 = P2 / ( 100.0 );
memset ( dp , 0 , sizeof ( dp ));
rep ( i , N + 1 )
dp [ i ][ 0 ] = 1.0 ;
REP ( i , 1 , N + 1 ) {
REP ( j , 1 , W + 1 ) {
if ( j - 2 >= 0 ) {
dp [ i ][ j ] = max ( dp [ i ][ j ], p1 * dp [ i - 1 ][ j - 2 ] + ( 1 - p1 ) * dp [ i - 1 ][ j ]);
} else {
dp [ i ][ j ] = max ( dp [ i ][ j ], p1 + ( 1 - p1 ) * dp [ i - 1 ][ j ]);
}
if ( j - 3 >= 0 ) {
dp [ i ][ j ] = max ( dp [ i ][ j ], p2 * dp [ i - 1 ][ j - 3 ] + ( 1 - p2 ) * dp [ i - 1 ][ j ]);
} else {
dp [ i ][ j ] = max ( dp [ i ][ j ], p2 + ( 1 - p2 ) * dp [ i - 1 ][ j ]);
}
}
}
return dp [ N ][ W ] * 100 ;
}
};