N个盒子围成一圈，第i个盒子初始时有Ai个小球，每次可以把一个小球从一个盒子移到相邻的两个盒子之一里。问最少移动多少次使得每个盒子中小球的个数不超过1。
ΣAi<=N.1<=N<=1000.
最小费用最大流。
每个盒子作为一个点。
若Ai>1则从源点向此点连一条容量为Ai，费用为0的边。
若Ai=0则从此点向汇点连一条容量为1，费用为0的边。
每个盒子向相邻的两个盒子连容量为正无穷，费用为1的边。
最小费用最大流即为答案。
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
const int dian=;
const int bian=;
const int INF=0x3f3f3f3f;
int h[dian],nxt[bian],ver[bian],val[bian],cos[bian],with[dian],minn[dian];
int d[dian],v[dian];
int map[dian];
int n,tot;
int S,T;
void add(int a,int b,int c,int d){
tot++;ver[tot]=b;val[tot]=c;cos[tot]=d;nxt[tot]=h[a];h[a]=tot;
tot++;ver[tot]=a;val[tot]=;cos[tot]=-d;nxt[tot]=h[b];h[b]=tot;
}
bool tell(){
memset(v,,sizeof(v));
memset(d,0x3f,sizeof(d));
memset(with,,sizeof(with));
memset(minn,0x3f,sizeof(minn));
queue<int>q;
q.push(S);
v[S]=;
d[S]=;
while(!q.empty()){
int x=q.front();
q.pop();
v[x]=;
for(int i=h[x];i;i=nxt[i]){
int y=ver[i];
if(d[y]>d[x]+cos[i]&&val[i]){
d[y]=d[x]+cos[i];
minn[y]=min(minn[x],val[i]);
with[y]=i;
if(!v[y]){
v[y]=;
q.push(y);
}
}
}
}
if(d[T]==0x3f3f3f3f)
return ;
return ;
}
int zeng(){
for(int i=T;i!=S;i=ver[with[i]^]){
val[with[i]]-=minn[T];
val[with[i]^]+=minn[T];
}
return minn[T]*d[T];
}
int dinic_cost(){
int r=;
while(tell())
r+=zeng();
return r;
}
int main(){
int cas;
scanf("%d",&cas);
while(cas--){
memset(h,,sizeof(h));
memset(nxt,,sizeof(nxt));
tot=;
scanf("%d",&n);
S=n+,T=n+;
for(int i=;i<=n;i++)
scanf("%d",&map[i]);
for(int i=;i<=n;i++){
if(map[i]>)
add(S,i,map[i]-,);
else if(!map[i])
add(i,T,,);
add(i,(i==)?n:i-,INF,);
add(i,(i==n)?:i+,INF,);
}
printf("%d\n",dinic_cost());
}
return ;
}