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; }