PKU 3639 Exchange Rates

問題

明日からn日間の米ドルとカナダドルのレートがわかっている。
取引には、3%の手数料がかかり、更に1セント未満は切り捨てられる。

今1000カナダドルを持っているとき、n日後、最大カナダドルをいくらに出来るか、求めよ。

制約条件

n≦365

方針

dp[i][j]: i日目の取引を終えて、j = 0ならカナダドルj = 1なら米ドルが最大いくら持てるか
のO(n)のDPをすればいい。

入出力にcin, coutを使うと500msくらいかかってギリギリになる。
1セント未満が切り捨てられることを忘れててはまる。

ソースコード

int n;
double r[400];
int dp[400][2];

int main()
{
	while(cin >> n, n){
		rep(i, n) cin >> r[i];
		rep(i, n) dp[i][0] = dp[i][1] = 0;
		dp[0][0] = 100000;
		
		for(int i = 1; i <= n; i++){
			dp[i][0] = max(dp[i - 1][0], (int)(dp[i - 1][1] * r[i - 1] * 0.97));
			dp[i][1] = max(dp[i - 1][1], (int)(dp[i - 1][0] / r[i - 1] * 0.97));
		}
		printf("%.2f\n", dp[n][0] / 100.0);
	}
	return 0;
}