AOJ 2305 - Beautiful Currency

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2305

概要

N 種類の貨幣があり，それぞれ価値は a[1], ..., a[N] である．

すべての i (1 <= i <= N-1) について，a[i+1] % a[i] == 0 となるとき，beautiful であるという．

ある貨幣の価値を a[i] から b[i] に変えたときの confution ratio を |a[i] - b[i]|/a[i] と定義する． confusion ratio の最大値が最小になるように a[1], ..., a[N] を beautiful に変えたとき，そのときの confusion ratio の最大値を答える．

制約

• 1 <= N <= 20
• 1 <= a[i] < a[2] < ... < a[N] < 10^5

解法

dp[i][i 番目の貨幣の変更後の価値] = confusion ratio の最大値

という DP． 「i 番目の貨幣の変更後の価値」の最大値は 10^5 ではない点に注意． とりあえず2倍の 2 * 10^5 にして通った．

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cmath>
 4 #include <algorithm>
 5 using namespace std;
 6 static const int M = 200000;
 7 
 8 int main()
 9 {
10   int N;
11   cin >> N;
12   int a[20];
13   for (int i = 0; i < N; i++) {
14     cin >> a[i];
15   }
16 
17   static double dp[20][M];
18   for (int i = 0; i < N; i++) {
19     fill_n(dp[i], M, 1e10);
20   }
21   for (int i = 1; i < M; i++) {
22     dp[0][i] = fabs(a[0] - i)/double(a[0]);
23   }
24   for (int i = 0; i < N-1; i++) {
25     for (int j = 1; j < M; j++) {
26       for (int k = 1; k*j < M; k++) {
27         dp[i+1][k*j] = min(dp[i+1][k*j], max(dp[i][j], fabs(a[i+1] - k*j)/double(a[i+1])));
28       }
29     }
30   }
31 
32   double ans = 1e10;
33   for (int i = 1; i < M; i++) {
34     ans = min(ans, dp[N-1][i]);
35   }
36   printf("%.9f\n", ans);
37   return 0;
38 }