ABC-395-F - Smooth Occlusion （差分约束） · znzryb
## 思路讲解
将问题通过转化，Ui‘的取值范围是
$$
max(H-D_i，0)<=U_i'<=U_i
$$
那么我们其实就是要在这个范围内实现题目要求
$$
U_{i-1}'-X<=U_i'<=U_{i-1}'+X
$$
然后问这个H最大是多少。
其实这是一个比较经典的差分约束系统[https://oi-wiki.org/graph/diff-constraints/](https://oi-wiki.org/graph/diff-constraints/)
【算法讲解142【扩展】负环和差分约束】 [https://www.bilibili.com/video/BV1iNH9eREG3/?share_source=copy_web&vd_source=6ca0bc05e7d6f39b07c1afd464edae37](https://www.bilibili.com/video/BV1iNH9eREG3/?share_source=copy_web&vd_source=6ca0bc05e7d6f39b07c1afd464edae37)
差分约束做法参考以下题解
[https://www.luogu.com.cn/article/xxqmcpr3](https://www.luogu.com.cn/article/xxqmcpr3)
怎么去记这个连边的方向那（判断负环的话）
**这个小于等于号像不像一个箭头，这就是连边方向！**~~（奇淫巧技）~~
然后判断负环的话总归是小于号（不是小于嘛就变成小于，两边加符号嘛）。
然后其实这道题目默认是没有负环的（因为X是正值嘛），所以不用判断负环。
其实这两种方法殊途同归，因为他们得到的都是最靠近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](https://www.bilibili.com/video/BV1vE98YDEXA/?share_source=copy_web&vd_source=6ca0bc05e7d6f39b07c1afd464edae37&t=5879)
## AC代码
[https://atcoder.jp/contests/abc395/submissions/64194370](https://atcoder.jp/contests/abc395/submissions/64194370)
```cpp
// 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……）