Skip to content

Instantly share code, notes, and snippets.

@latte0119
Created September 12, 2016 13:33
Show Gist options
  • Save latte0119/144088346dc643a78db182f85aa3f5e1 to your computer and use it in GitHub Desktop.
Save latte0119/144088346dc643a78db182f85aa3f5e1 to your computer and use it in GitHub Desktop.
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;
#define fi first
#define se second
template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}
int n;
int p[5000];
int z[5000];
signed main(){
while(cin>>n,n){
rep(i,n)cin>>p[i];
int ans=1001001001ll;
for(int t=0;t<=p[0];t++){
int cost=t;
memset(z,0,sizeof(z));
z[0]=t;
for(int i=1;i<n;i++){
cost+=(p[i-1]-z[i-1])*2;
z[i]+=p[i-1]-z[i-1];
chmin(z[i],p[i]);
}
cost+=p[n-1]-z[n-1];
chmin(ans,cost);
}
cout<<ans<<endl;
}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment