Znzryb's Blog
0%

ABC-395-F - Smooth Occlusion （差分约束）

Posted on Edited on

思路讲解

将问题通过转化，Ui‘的取值范围是

max(H−Di，0)<=Ui′<=Uimax(H-D_i，0)<=U_i'<=U_i

那么我们其实就是要在这个范围内实现题目要求

Ui−1′−X<=Ui′<=Ui−1′+XU_{i-1}'-X<=U_i'<=U_{i-1}'+X

然后问这个H最大是多少。

其实这是一个比较经典的差分约束系统https://oi-wiki.org/graph/diff-constraints/

【算法讲解142【扩展】负环和差分约束】 https://www.bilibili.com/video/BV1iNH9eREG3/?share_source=copy_web&vd_source=6ca0bc05e7d6f39b07c1afd464edae37

差分约束做法参考以下题解

https://www.luogu.com.cn/article/xxqmcpr3

image

怎么去记这个连边的方向那（判断负环的话）

这个小于等于号像不像一个箭头，这就是连边方向！

这个小于等于号像不像一个箭头，这就是连边方向！（奇淫巧技）

然后判断负环的话总归是小于号（不是小于嘛就变成小于，两边加符号嘛）。

然后其实这道题目默认是没有负环的（因为X是正值嘛），所以不用判断负环。

https://www.luogu.com.cn/article/hm6gtuo1

其实这两种方法殊途同归，因为他们得到的都是最靠近0的点，只不过一个是从左边接近，一个从右边接近，说白了这两个解的转化无非就是+d的事情。

但是好像这两种办法对这题其实没什么帮助。我们需要的解其实是最靠近原来的长度的解，这样可以保证Ui被磨的最少，这样子H自然会更大。

所以我们把距离初始值设定为Ui，然后只往小里面更新，不往大里面更新（因为是小于号系统，不往小里面更新会不满足系统约束）

官解以及视频题解都是二分答案做法，但是我总归还是想学一点新的东西嘛。

参考以下视频题解

【AtCoder 初学者竞赛 395比赛讲解（ABC395）】 【精准空降到 1:37:59】 https://www.bilibili.com/video/BV1vE98YDEXA/?share_source=copy_web&vd_source=6ca0bc05e7d6f39b07c1afd464edae37&t=5879

image

AC代码

https://atcoder.jp/contests/abc395/submissions/64194370

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
// Problem: F - Smooth Occlusion
// Contest: AtCoder - AtCoder Beginner Contest 395
// URL: https://atcoder.jp/contests/abc395/tasks/abc395_f
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,2> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(5e18)+3;

ll N,X,T;
arr ud[MAXN];

struct cmp{
	bool operator()(const arr &a,const arr &b)const{
		return a[1]>b[1];
	}
};

inline void solve(){
	cin>>N>>X;
	ll minH=0,maxH=INF,sumUd=0;
	vector<ll> dist(N+5,INF);
	vector<vector<ll> > g(N+5);
	vector<bool> vis(N+5,false);
	priority_queue<arr,vector<arr>,cmp> q;
	FOR(i,1,N){
		cin>>ud[i][0]>>ud[i][1];
		maxH=min(maxH,(ud[i][0]+ud[i][1]));
		sumUd+=(ud[i][0]+ud[i][1]);
		if(i!=N) g[i+1].pb(i),g[i].pb(i+1);
		dist[i]=ud[i][0];
		q.push({i,dist[i]});
	}
	// 在这个差分约束上走最短路（Dijsktra）
	while(!q.empty()){
		ll u=q.top()[0],dis=q.top()[1];
		q.pop();
		if(vis[u]) continue;
		vis[u]=true;
		dist[u]=dis;
		FOR(i,0,SZ(g[u])-1){
			ll v=g[u][i];
			if(!vis[v]){
				q.push({v,dis+X});
			}
		}
	}
// #ifdef LOCAL
    // FOR(i,1,N){
    	// cerr<<dist[i]<<' ';
    // }
    // cerr<<"\n";
// #endif
	ll H=INF;
	FOR(i,1,N){
		H=min(H,dist[i]+ud[i][1]);
	}
	cout<<sumUd-N*H<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	// cin>>T;
	// while(T--){
		// solve();
	// }
	solve();
	return 0;
}
/*
AC
https://atcoder.jp/contests/abc395/submissions/64194370
*/

心路历程（WA，TLE，MLE……）