aoj2305:Beautiful Currency

問題文

Beautiful Currency | Aizu Online Judge

解法

dp[i+1][j]:=先頭からi個まで変更し終わって、それら(先頭i個)はBeautifulになってて、末尾要素(変更後のa_iの値)がjであるときのコストの最小値、とする。1つめのパラメータは当然1からNまで見る。2つめのパラメータは1からKまで見ることにする。

配るdpをすることを考える。dp[i+1][j]から遷移する先は、dp[i+2][k](kはjの整数倍)である。このdpはO(N*K^2)に見える。各iごとにK/1+K/2+...+K/K=K(1/1+1/2+...+1/K)回程度の計算が必要になるが、1/1+1/2+...+1/K=O(logK)とかそんな感じになるので、実はK/1+K/2+...+K/K=O(KlogK)。全体でO(NKlogK)。

少し考えるとKは数列aの要素の最大値(10^5)の2倍程度にとっておけばとりあえず十分なので、K=2*10^5でやりました。

コード

#include<bits/stdc++.h>
using namespace std;

#define int long long
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define all(v) (v).begin(),(v).end()
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

int N;
int A[20];

double dp[2][200010];

signed main(){
    cin>>N;rep(i,N)cin>>A[i];

    fill_n(*dp,2*200010,1001001001);

    dp[0][1]=0;
    rep(i,N){
        reps(j,1,200000+1){
            for(int k=j;k<=200000;k+=j){
                double tmp=(double)abs(A[i]-k)/A[i];
                chmin(dp[(i+1)&1][k],max(dp[i&1][j],tmp));
            }
            dp[i&1][j]=1001001001;
        }
    }

    double mi=1001001001;
    reps(j,1,200000+1)chmin(mi,dp[N&1][j]);
    printf("%.20f\n",mi);
    return 0;
}