Algoogle

Algorithm for Programming Contest

AOJ 2305 Beautiful Currency

Category: AOJ Tag: dp

Beautiful Currency

問題概要


数列aの数値を変更してa[i+1]をa[i]が必ず割り切るような数列にしたい.
数値を変更したときにかかるコスト(|b-a|/a)の最大の最小はいくらか.

解法


dp[i][j] := i番目の数をjにする時のiまでのコストの最大の最小値

コード


(2305.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <bits/stdc++.h>
using namespace std;
#define repi(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define rep(i,a) repi(i,0,a)
const int inf = 1e9, M = 200001;
int N, a[32];
double dp[32][M];
inline double f(int x, int y){ return 1.*abs(x-y)/x;}

double solve(){
    rep(i,N) fill(dp[i],dp[i]+M,inf);
    repi(i,1,M) dp[0][i] = f(a[0],i);

    rep(i,N-1) repi(j,1,M) if(dp[i][j] < inf) for(int k = j; k < M; k += j)
        dp[i+1][k] = min(dp[i+1][k], max(dp[i][j], f(a[i+1],k)));
    double ans = inf;
    rep(i,M) ans = min(ans, dp[N-1][i]);
    return ans;
}

int main(){
    cin >> N;
    rep(i,N) cin >> a[i];
    printf("%.10f\n", solve());
    return 0;
}

Comments