0w1

POI 19 Fibonacci Representation ( DP )

http://main.edu.pl/en/archive/oi/19/roz

IDDFSで頑張ろうとしたが、当たり前にもTLEした。 24 / 100。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MAXK = 4e17 + 4;

int maxd;
vector< ll > fib;

bool dfs(ll k, int d){
    if( k == 0 ) return true;
    if( d == maxd ) return false;
    int idx = lower_bound( fib.begin(), fib.end(), -k ) - fib.begin();
    for(int i = idx; i < fib.size(); ++i){
        ll val = -fib[ i ];
        if( dfs( k - val, d + 1 ) ) return true;
    }
    for(int i = fib.size() - 1; i > idx; --i){
        ll val = -fib[ i ];
        if( dfs( k + val, d + 1 ) ) return true;
    }
    return false;
}

void preprocess(){
    ll f0 = 1, f1 = 2;
    fib.push_back( -f0 );
    fib.push_back( -f1 );
    while( true ){
        if( f0 + f1 > MAXK ) break;
        ll tmp = f0 + f1;
        fib.push_back( -tmp );
        f0 = f1, f1 = tmp;
    }
    sort( fib.begin(), fib.end() );
}

int main(){
    preprocess();
    int T; scanf("%d", &T);
    while( T-- ){
        ll k; scanf("%lld", &k);
        for( maxd = 1; ; ++maxd )
            if( dfs( k, 0 ) )
                break;
        printf("%d\n", maxd);
    }
    return 0;
}

フィボナッチ数列の性質をちょっと考えて、0になる前はフィボナッチ数でなければいけないので、目的の数を何にするかという感じに状態を決められそうです。今の数を fib[ i ] < x < fib[ i + 1 ] だとすると、最小操作数を実現する場合は xは fib[ i ]か fib[ i + 1 ]にしかなり得ない( もし fib[ i + 2 ]にした方がいいなら fib[ i + 2 ] - fib[ i + 1 ] = fib[ i ] という fib[ i ]が無駄に加算される )。よって隣のフィボナッチ数を計算するだけで十分です。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MAXK = 4e17 + 4;

vector< ll > fib;

map< ll, int > memo;

int dp(ll k){
    if( k == 0LL ) return 0;
    if( memo.count( k ) ) return memo[ k ];
    int idx = upper_bound( fib.begin(), fib.end(), k ) - fib.begin();
    return memo[ k ] = min( dp( k - fib[ idx - 1 ] ), dp( fib[ idx ] - k ) ) + 1;
}

void preprocess(){
    ll f0 = 1, f1 = 2;
    fib.push_back( f0 );
    fib.push_back( f1 );
    while( true ){
        if( f0 + f1 > 2 * MAXK ) break;
        ll tmp = f0 + f1;
        fib.push_back( tmp );
        f0 = f1, f1 = tmp;
    }
    sort( fib.begin(), fib.end() );
}

int main(){
    int T; scanf("%d", &T);
    preprocess();
    while( T-- ){
        ll k; scanf("%lld", &k);
        printf("%d\n", dp( k ));
    }
    return 0;
}