【HDOJ】1903 Exchange Rates

mindong

　　水DP。精度很坑。



1 /* hdoj 1903 */
2 #include <cstdio>
3 #include <cstring>
4 #include <cstdlib>
5 #include <cmath>
6
7 #define MAXN 505
8
9 double a[MAXN];
10 double dp[MAXN][2];
11
12 double max(double a, double b) {
13     return a>b ? a:b;
14 }
15
16 inline double cal(double x, double f) {
17     return floor(x*f*0.97*100.)/100.0;
18 }
19
20 int main() {
21     int t, n;
22     int i, j, k;
23     double tmp;
24     
25     #ifndef ONLINE_JUDGE
26         freopen("data.in", "r", stdin);
27     #endif
28     
29     while (scanf("%d", &n)!=EOF && n) {
30         for (i=1; i<=n; ++i)
31             scanf("%lf", &a);
32         dp[0][0] = 0.0;
33         dp[0][1] = 1000.0;
34         for (i=1; i<=n; ++i) {
35             dp[0] = max(dp[i-1][0], cal(dp[i-1][1], 1./a));
36             dp[1] = max(dp[i-1][1], cal(dp[i-1][0],    a));
37         }
38         printf("%.2lf\n", dp[n][1]);
39     }
40     
41     return 0;
42 }