読者です 読者をやめる 読者になる 読者になる

SRM 501 Div2 Medium

他人のソース見てて気づいたけどdp解法これだけでいいわ。マイナスとかプラスとか状態分けしなくてよくて、最小・最大で状態分けすればいいだけだった。

class FoxPlayingGame {
public:
	double theMax(int nA, int nB, int paramA, int paramB) {
		double sA = paramA/1000.0 , sB = paramB/1000.0;
		double dp[51][51][2] = {0};
		rep(i,51)rep(j,51)dp[i][j][0] = 1e20;
		rep(i,51)rep(j,51)dp[i][j][1] = -1e20;
		dp[nA][nB][0] = dp[nA][nB][1] = 0;
		for(int i=nA;i>=0;i--){
			for(int j=nB;j>=0;j--){
				for(int k=0;k<2;k++){
					if(i)dp[i-1][j][1] = max(dp[i][j][k]+sA,dp[i-1][j][1]);
					if(i)dp[i-1][j][0] = min(dp[i][j][k]+sA,dp[i-1][j][0]);
					if(j)dp[i][j-1][1] = max(dp[i][j][k]*sB,dp[i][j-1][1]);
					if(j)dp[i][j-1][0] = min(dp[i][j][k]*sB,dp[i][j-1][0]);
				}
			}
		}
		return dp[0][0][1];
	}
};