SRM420 div1 medium
DP[r][b]=max(r-b,赤を引く確率*DP[r+1][b]+黒を引く確率*DP[r][b+1])でDP。
そのままメモリに取るとMLEするので、r+1またはb+1しかない性質を利用してメモリを節約。
#include <algorithm> using namespace std; class RedIsGood { public: double getProfit(int R, int B) { double DP[2][5010]; for(int i=0;i<=B+1;i++) DP[(R+1)%2][i]=0.0; for(int r=R;0<=r;r--) { for(int b=B;0<=b;b--) { double red=(double)(R-r)/(double)((R+B)-(r+b)); double a=red*DP[(r+1)%2][b]+(1.0-red)*DP[r%2][b+1]; DP[r%2][b]=max((double)r-b,a); } DP[r%2][B+1]=0.0; } return DP[0][0]; } };
あと84問