ccf201809-4

发表于 | 分类于 | 阅读数 次

链接:ccf201809-4

题解

  • 简单的差分约束，给出的是形如,前缀和一下就是简单的差分约束
  • 求最小字典序即前缀和最小，求最长路即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<bits/stdc++.h>
#define rep(i,x,y) for(register int i=x;i<=y;++i)
#define repd(i,x,y) for(register int i=x;i>=y;--i)
#define ll long long
using namespace std;
const int N=1e5+7;
const int inf=0x3f3f3f3f;
template<typename T>inline void read(T &x){
	char c;int sign=1;x=0;
	do{c=getchar();if(c=='-')sign=-1;}while(c<'0'||c>'9');
	do{x=x*10+c-'0';c=getchar();}while(c>='0'&&c<='9');
	x*=sign;
}
int dis[N],nxt[N],w[N],to[N],head[N],inq[N],cnt,n;
inline void adde(int a,int b,int c){
	w[++cnt]=c;
	to[cnt]=b;
	nxt[cnt]=head[a];
	head[a]=cnt;
}
inline void init(){
	read(n);
	rep(i,1,n){
		int x;read(x);
		if(i==1){adde(i+1,i-1,-2*x-1);adde(i-1,i+1,2*x);}
		else if(i==n){adde(i,i-2,-2*x-1);adde(i-2,i,2*x);}
		else{adde(i+1,i-2,-3*x-2);adde(i-2,i+1,3*x);}
		adde(i-1,i,1);
	}
}
queue<int>q;
void spfa(){
	memset(dis,0,sizeof dis);
	q.push(0);
	inq[0]++;dis[0]=0;
	while(!q.empty()){
		int k=q.front();q.pop();
		inq[k]--;
		for(int i=head[k],v;i;i=nxt[i]){
			if(dis[v=to[i]]>=dis[k]+w[i])continue;
			dis[v]=dis[k]+w[i];
			if(!inq[v]){q.push(v);inq[v]++;}
		}
	}
}
int main(){
	init();
	spfa();
	rep(i,1,n)printf("%d%c",dis[i]-dis[i-1],i==n?'\n':' ');
	return 0;
}