P7730 [JDWOI-1] 蜀道难

首先，区间增加定值并且要求单调不降，很容易想到差分。

于是先把 \(h\) 数组差分一下，题目的要求即为最小代价使得 \(h\) 均为非负数。

观察一下两种操作，发现 \(n\) 的范围很小，可以枚举操作的起点 \(i\) ，然后如果操作是压低，相当于 \(h[i]--,h[i+l[i]]++\) 。

而如果操作是抬高，相当于 \(h[i]++,h[i+l[i]]--\) 。

显然差分数组的总和是一定的（边界有点小问题下文会提及），那么可以把压低当成一条 \(i\) 到 \(i+l[i]\) 的流，抬高也是同理。

注意当 \(i+l[i]-1\) 恰好为 \(n\) 时 \(i+l[i]\) 为 \(n+1\) 但是这个操作显然是合法的，所以要增加一个 \(n+1\) 号点， \(h[n+1]\) 设为 \(h\) 的上限。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=200010;
const int INF=1000000000;
int increase[N],to[N],head[N];
int flow[N],cost[N],nxt[N];
int pre[N];
int maxflow,tot;
bool vis[N];
int dis[N];
int n,m,s,t,ans,a,b;
int h[N];void add(int x,int y,int z,int c){to[++tot]=y;flow[tot]=z;cost[tot]=c;nxt[tot]=head[x];head[x]=tot;to[++tot]=x;flow[tot]=0;cost[tot]=-c;nxt[tot]=head[y];head[y]=tot;
}bool spfa(){memset(increase,0x3f,sizeof(increase));memset(vis,0,sizeof(vis));memset(dis,0x3f,sizeof(dis));int kep=dis[t];dis[s]=0;queue<int> q;q.push(s);vis[s]=true;while(!q.empty()){int x=q.front();q.pop();vis[x]=false;for(int i=head[x];i;i=nxt[i]){int y=to[i];if(flow[i] && dis[y]>dis[x]+cost[i]){dis[y]=dis[x]+cost[i];increase[y]=min(increase[x],flow[i]);pre[y]=i;if(!vis[y]){vis[y]=true;q.push(y);}}}}return dis[t]<kep;
}void update(){int cur=t;while(cur!=s){int last=pre[cur];flow[last]-=increase[t];flow[last^1]+=increase[t];cur=to[last^1];}maxflow+=increase[t];ans+=(increase[t]*dis[t]);
}inline int read(){char ch;int x=0;bool f=false;for(;!isdigit(ch);ch=getchar())if(ch=='-')f=true;for(;isdigit(ch);ch=getchar())x=(x<<1)+(x<<3)+(ch^48);if(f) x=-x;return x;
}signed main(){cin>>n>>m;s=0,t=n+2;h[n+1]=10000;tot=1;for(int i=1;i<=n;i++){h[i]=read();}for(int i=n;i>=1;i--){h[i]-=h[i-1];}char c;for(int i=1;i<=m;i++){cin>>c;a=read(),b=read();for(int j=1;j<=n-a+1;j++){int k=j+a;if(c=='-') add(j,k,INF,b);else add(k,j,INF,b);}}for(int i=1;i<=n+1;i++){//cout<<"h[i]: "<<i<<" "<<h[i]<<"\n";add(s,i,h[i]+1001,0),add(i,t,1001,0);}while(spfa()){update();}if(maxflow!=1001*(n+1)) cout<<-1;else cout<<ans;return 0;
}