土下座しながら探索中

主に競技プログラミング

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