Codeforces Global Round 2 E. Pavel and Triangles(貪心+DP思想)*

題目連結:http://codeforces.com/contest/1119/problem/E

題目大意

給定價值為2的幂次方的長度的數量序列，

問最多能拼成多少個合法三角形。

題目分析 

不難利用幂次方級數的性質發現，

構成三角形隻有兩種情況，

三種選一樣的，和兩個一樣的加上一個次小的。

基于這樣的情況，我們考慮目前位置數量，

按2選取的話肯定是貪心的能選多少就選多少，

但我們要維護一個剩餘量，對于這個剩餘量貪心很明顯，

因為現在把2用掉政策肯定由于把2丢到剩餘量中，

我們不難想到對于每一個位置我們要把剩餘量量壓榨幹淨是以

先貪心的選取2，

關鍵是剩餘的，我們到底用不用3來增益答案，

因為我們一個3丢到剩餘堆中，可以以後有2，2，2這樣的情況來

構成3個的答案效果，但我們發現狀态可以劃分成3和2，2，2，

而3，2，2中掃描到最後剩餘量兩種政策都是1，答案也一樣，肯定是貪心政策好，

3，2也是一樣，是以我們把2貪心的選取完後再貪心的選取3.。。。。

這道題我是看了題解的，，，非常不爽就被這樣的戲弄了。。。

自己對于DP和貪心性質的了解還是需要加強。

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

#define debug puts("YES");
#define rep(x,y,z) for(int (x)=(y);(x)<(z);(x)++)
#define ll long long

#define lrt int l,int r,int rt
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define root l,r,rt
#define mst(a,b) memset((a),(b),sizeof(a))
#define pii pair<int,int>
#define fi first
#define se second
#define mk(x,y) make_pair(x,y)
const int mod=1e9+7;
const int maxn=1e5+100;
const int ub=1e6;
ll powmod(ll x,ll y){ll t; for(t=1;y;y>>=1,x=x*x%mod) if(y&1) t=t*x%mod; return t;}
ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}
/*
題目大意：
給定價值為2的幂次方的長度的數量序列，
問最多能拼成多少個合法三角形。

題目分析：
不難利用幂次方級數的性質發現，
構成三角形隻有兩種情況，
三種選一樣的，和兩個一樣的加上一個次小的。
基于這樣的情況，我們考慮目前位置數量，
按2選取的話肯定是貪心的能選多少就選多少，
但我們要維護一個剩餘量，對于這個剩餘量貪心很明顯，
因為現在把2用掉政策肯定由于把2丢到剩餘量中，
我們不難想到對于每一個位置我們要把剩餘量量壓榨幹淨是以
先貪心的選取2，
關鍵是剩餘的，我們到底用不用3來增益答案，
因為我們一個3丢到剩餘堆中，可以以後有2，2，2這樣的情況來
構成3個的答案效果，但我們發現狀态可以劃分成3和2，2，2，
而3，2，2中掃描到最後剩餘量兩種政策都是1，答案也一樣，肯定是貪心政策好，
3，2也是一樣，是以我們把2貪心的選取完後再貪心的選取3.。。。。
這道題我是看了題解的，，，非常不爽就被這樣的戲弄了。。。
自己對于DP和貪心性質的了解還是需要加強。
*/
ll n,x;
ll res=0,ans=0;
int main(){
    cin>>n;
    rep(i,0,n){
        cin>>x;
        ll tmp=min(res,x/2);
        res-=tmp,x-=tmp*2;
        ans+=tmp+x/3;
        res+=x%3;
    }
    cout<<ans<<endl;
    return 0;
}