P7730 [JDWOI-1] 蜀道难

为什么这题还不错却没人写题解啊。

考虑序列不降时有什么性质：\(a_i-a_{i-1}\ge0,i\in(1,n]\)

考虑操作是区间同时加减，想到差分。

记 \(d_1=a_1,d_i=a_i-a_{i-1},i\in(1,n]\)，那么我们要让 \(d_i\ge0,i\in[1,n]\)

每次操作即

di--,dj++
di++,dj--

那么对于 \(d_i>0\) 的，可以最多减 \(d_i\) 次，提供 \(d_i\) 次加的机会，对于 \(d_i<0\) 的，至少被加 \(|d_i|\) 次，需要 \(d_i\) 次被加。显然转化为二分图之后最小费用最大流。

但是假如只规定正权点向负权点提供流量是不够的，因为可能长度无法匹配导致我们对于 \(i,j,d_i>0,d_j<0\) 需要 \(k\) 来先让 \(i,k\) 操作，再让 \(k,j\) 操作来实现。

所以我们要对于每个区间，无论左右是什么点，都连。

代码

#include 
using namespace std;
int rd() {
    int f=1,sum=0; char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') f=-1; ch=getchar();}
    while(isdigit(ch)) {sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
    return sum*f;
}

#define N (int)(5e4+5)
#define inf (int)(2e9)
struct edge {
	int nex,to,w,c;
}e[N<<1];
int hea[N],cnt=1;
int mic[2][N],bian[N];
int n,m,S,T,tot,a[N],b[N],ans;

void add_edge(int x,int y,int z,int c) {
	e[++cnt].nex=hea[x]; e[cnt].to=y; e[cnt].w=z; e[cnt].c=c; hea[x]=cnt;
}

void add(int x,int y,int z,int c) {
	add_edge(x,y,z,c); add_edge(y,x,0,-c);
}

dequeq;
bool vis[N];
int dis[N];
bool spfa() {
	for(int i=0;idis[x]+e[i].c) {
				dis[y]=dis[x]+e[i].c;
				if(!vis[y]) {
					vis[y]=1;
					if(!q.empty()&&dis[y]>op; x=rd(); y=rd();
		if(op=='+') op=0; else op=1;
		mic[op][x]=min(mic[op][x],y);
	}
	add(S,n+1,inf,0);
	for(int i=1;i<=n;i++) {
		if(a[i]>0) {
			add(S,i,a[i],0);
		} else {
			add(i,T,-a[i],0); bian[++tot]=cnt-1;
		}
	}
	for(int i=1;i<=n;i++) {
		for(int l=1,r=l+i;r<=n+1;l++,r=l+i) {
			if(mic[0][i]