問題
http://community.topcoder.com/stat?c=problem_statement&pm=9915
赤いカードがＲ枚、青のカードがＢ枚存在する。
最初にカードは伏せられており、１枚選んでひっくり返す。
ひっくり返したカードが赤ならスコアが＋１、青ならー１となる。
プレイヤーは任意のプレイ回数でプレイをやめてもよい。
このとき、プレイヤーが得られるスコアの最大の期待値を求める。
解き方
まずはスコアの計算方法を紙に書いて整理してみた。
現在持っている赤のカード枚数rと青のカード枚数bであるとき
そのときのスコアdp[r][b]は
(dp[r-1][b]+1) *r/(r+b) +(dp[r][b-1]-1)*b/(r+b)もしくは0のうち最大のものになる。
ただし、カード枚数はそれぞれ5000枚なので5000*5000はメモリに保存できない。
ここで上記の式を考えると
「dp[r-1][b]＝ひとつ前の配列」と「dp[r][b-1]＝現在の配列」の２つだけを持っているだけでよいので、2*5000となりメモリ量も足りる。
コード
using namespace std;
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
double dp[2][5001];
class RedIsGood {
public:
double getProfit(int R, int B) {
memset(dp,0,sizeof(dp));
int old=0,cur=1;
FORE(i,1,R+1){
dp[cur][0]=i;
FORE(j,1,B+1){
dp[cur][j]=max(0.0,(double)(i*(dp[old][j]+1.0)+j*(dp[cur][j-1]-1.0))/(i+j));
}
swap(old,cur);
}
return dp[old][B];
}
};
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
double dp[2][5001];
class RedIsGood {
public:
double getProfit(int R, int B) {
memset(dp,0,sizeof(dp));
int old=0,cur=1;
FORE(i,1,R+1){
dp[cur][0]=i;
FORE(j,1,B+1){
dp[cur][j]=max(0.0,(double)(i*(dp[old][j]+1.0)+j*(dp[cur][j-1]-1.0))/(i+j));
}
swap(old,cur);
}
return dp[old][B];
}
};