原题链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1061
题意：问你如何购买志愿者使得满足题意的总费用最小。
解题思路：首先，由于志愿者存在的时间是一个区间，我们考虑使用差分序列，这样的话我们就可以比较轻松的建图跑一遍最小费用最大流了。我们定义每个中间点代表着每一天，显然第i天需要的志愿者是i-1天的志愿者+x，用差分即可完成。建图方式详见AC代码。
附：AC代码（因为我比较蒻，所以打了low的一逼的SPFAcostflow，所以跑的巨慢。）
#include<stdio.h>
#include<string.h>
#define S 0
#define T 1002
#define MAXN 1005
#define inf 0x7fffffff
#define min(a,b) (a<b?a:b)
struct zxy{int to,next,v,c;}edge[];
int n,m,cnt=,head[MAXN],dis[MAXN],pre[MAXN],que[MAXN];
bool vis[MAXN];
inline void ins(int x,int y,int v,int l){
edge[++cnt].to=y,edge[cnt].c=l,edge[cnt].v=v,edge[cnt].next=head[x],head[x]=cnt;
}
inline void insw(int x,int y,int v,int l){ins(x,y,v,l); ins(y,x,,(-)*l);}
inline int in(){
int x=,f=;char ch=getchar();
while(ch<''||ch>'') f=ch=='-'?-:,ch=getchar();
while(ch>=''&&ch<='') x=x*+ch-'',ch=getchar();
return x*f;
}
inline bool SPFA_costflow(int s,int e){
register int h=,t=,w,v;
memset(dis,/,sizeof(dis));
dis[s]=,vis[s]=,que[]=s;
while(h!=t){
(++h)%=MAXN;
w=que[h];
for (register int i=head[w]; i; i=edge[i].next){
v=edge[i].to;
if (dis[v]>dis[w]+edge[i].c&&edge[i].v){
dis[v]=dis[w]+edge[i].c;pre[v]=i;
if (!vis[v]){
vis[v]=;
if (dis[v]<dis[que[h+]]){
que[h]=v;h=(h-+MAXN)%MAXN;
}
else{
(++t)%=MAXN;que[t]=v;
}
}
}
}
vis[w]=;
}
return dis[e]!=dis[MAXN-];
}
int costflow(int s,int t){
int cost=;
while(SPFA_costflow(s,t)){
int mi=inf;
for (register int i=t; i; i=edge[pre[i]^].to)
mi=min(mi,edge[pre[i]].v);
for (register int i=t; i; i=edge[pre[i]^].to)
edge[pre[i]].v-=mi,edge[pre[i]^].v+=mi;
cost+=mi*dis[t];
}
return cost;
}
void init(){
n=in(),m=in();int x=,pre=;
for (int i=; i<=n; ++i){
register int t=in(); x=t-pre;pre=t;
if (x>) insw(S,i,x,);
else insw(i,T,(-)*x,);
insw(i+,i,inf,);
}
insw(n+,T,inf,);
for (register int i=; i<=m; ++i){
register int l=in(),r=in(),v=in();
insw(l,r+,inf,v);
}
}
int main(){
init();
printf("%d",costflow(S,T));
}