UVa 13039 : Fibonacci Triangle
問題リンク :
https://uva.onlinejudge.org/external/130/13039.pdf
問題概要 :
1番目のフィボナッチ数を2, 2番目のフィボナッチ数を3とする
i番目のフィボナッチ数と同じ長さの線分がそれぞれa[i]個存在する
これらの線分を使って作れる三角形の本数の最大値を求めよ
解法 :
これもlaycrsさんの解説をみて解いた
三角形のうち一番長い線分の長さをF、Fの1つ前のフィボナッチ数の長さをF1とする
この時に考えられる三角形の構成は次のとおり
1. F が3本
2. F が2本 + なんでも良いので1本
3. F が1本 + F1が2本
短い線分から順番に三角形を作っていくことを考えたとき、
最大の辺の長さより前のものをできる限り消費したいので、
3,2,1の順番で三角形を作っていくとよい
コード:
nclude<bits/stdc++.h> #define REP(i,s,n) for(int i=s;i<n;i++) #define rep(i,n) REP(i,0,n) using namespace std; typedef long long ll; int main() { int T; cin >> T; while( T-- ) { int n; cin >> n; vector<ll> vec(n); rep(i,n) cin >> vec[i]; ll sum = 0, prev = 0; rep(i,n) { while( i-1 >= 0 && vec[i] && vec[i-1] >= 2LL ) { vec[i-1] -= 2LL, prev -= 2LL, --vec[i]; ++sum; } while( prev && vec[i] >= 2LL ) { vec[i] -= 2LL, --prev; ++sum; } while( vec[i] >= 3LL ) { vec[i] -= 3LL; ++sum; } prev += vec[i]; } cout << sum << endl; } return 0; }