套路题
以样例为例，设第\(i\)个位置放置\(a_i\)个炮塔。
列出线性规划。
\(0a_1+1a_2+1a_3+0a_4+0a_5\geq 1\)
\(1a_1+1a_2+1a_3+1a_4+1a_5\geq 4\)
\(0a_1+0a_2+1a_3+1a_4+1a_5\geq 2\)
最小化\(1a_1+5a_2+6a_3+3a_4+4a_5,a_i\geq 0\)
对偶
\(0a_1+1a_2+0a_3\geq 1\)
\(1a_1+1a_2+0a_3\geq 5\)
\(1a_1+1a_2+1a_3\geq 6\)
\(0a_1+1a_2+1a_3\geq 3\)
\(0a_1+1a_2+1a_3\geq 4\)
最大化\(1a_1+4a_2+2a_3,a_i\geq 0\)
这事实上等于：可以把区间\([l_i,r_i]\)无限次\(+1\)，价值\(d_i\)，每个位置最多被加\(c_i\)次，求最大价值。
\(0a_1+1a_2+0a_3-b_1=1\)
\(1a_1+1a_2+0a_3-b_2=5\)
\(1a_1+1a_2+1a_3-b_3=6\)
\(0a_1+1a_2+1a_3-b_4=3\)
\(0a_1+1a_2+1a_3-b_5=4\)
\(b_i\geq 0\)
添加两条方程，差分
\(0a_1+1a_2+0a_3-b_1=1\)
\(1a_1+0a_2+0a_3-b_2+b_1=4\)
\(0a_1+0a_2+1a_3-b_3+b_2=1\)
\(-1a_1+0a_2+0a_3-b_4+b_3=-3\)
\(0a_1+0a_2+0a_3-b_5+b_4=1\)
\(0a_1+0a_2+0a_3+b_5=-4\)
容易发现每个数出现\(1\)次，且为一正一负。
把每个常量向s,t连边即可。
不知道为什么tle。
#include<bits/stdc++.h>
using namespace std;
#define N 1200010
int h[N],nxt[N],v[N],ct,w[N],s,t,pre[N],dis[N],pa[N],ec,ans,co[N],inq[N],n,m,c[N];
void add(int a,int b,int c,int d){v[++ec]=b;w[ec]=c;nxt[ec]=h[a];co[ec]=d;h[a]=ec;}
void adj(int a,int b,int c,int d){
add(a,b,c,d);
add(b,a,0,-d);
}
bool bfs(){
for(int i=0;i<=t;i++){
dis[i]=1999999999;
pre[i]=-1;
}
dis[s]=0;
queue<int>q;
q.push(s);
inq[s]=1;
while(!q.empty()){
int x=q.front();
q.pop();
inq[x]=0;
for(int i=h[x];i;i=nxt[i])
if(w[i]>0&&co[i]+dis[x]<dis[v[i]]){
dis[v[i]]=co[i]+dis[x];
pa[v[i]]=i;
pre[v[i]]=x;
if(!inq[v[i]]){
inq[v[i]]=1;
q.push(v[i]);
}
}
}
if(pre[t]==-1)
return false;
return true;
}
int mcmf(){
int c=0,f=0;
while(bfs()){
int fl=1e9;
for(int i=t;s!=i;i=pre[i])
fl=min(fl,w[pa[i]]);
f+=fl;
c+=fl*dis[t];
for(int i=t;i!=s;i=pre[i])
w[pa[i]]-=fl,w[pa[i]^1]+=fl;
}
return c;
}
int main(){
ec=1;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&c[i]);
t=n+2;
for(int i=1;i<=n+1;i++){
if(c[i]-c[i-1]>0)
adj(s,i,c[i]-c[i-1],0);
else
adj(i,t,c[i-1]-c[i],0);
}
for(int i=1;i<=n;i++)
adj(i,i+1,1e9,0);
for(int i=1;i<=m;i++){
int l,r,v;
scanf("%d%d%d",&l,&r,&v);
adj(l,r+1,1e9,-v);
}
printf("%d",-mcmf());
}