【CF1066F】Yet another 2D Walking 题解
此题可以用动态规划求解。
题目描述
题目链接here
小M在平面直角坐标系上的(0,0)点。他每次可以向上下左右走一格。
如果两个点满足max(Xi,Yi)≤max(Xj,Yj)，那么从i到j就有一条有向路径。
定义两点的距离为曼哈顿距离。
最小化路径长度。
核心思路
我们将所有的点按照max(x,y)分层，就如上图所示。可以证明只有到达某一层并且将该层完全走完再走下一层是最优的。
定义dpi,0表示到达第i条边的左端点的最小路径，dpi,1表示到达第i条边的右端点的最小路径。
转移方程显然。
dpi,1dpi,0=min(dpi−1,1+dist(righti−1,lefti),dpi−1,0+dist(lefti−1,lefti))+disi−1;=min(dpi−1,1+dist(righti−1,righti),dpi−1,0+dist(lefti−1,righti))+disi−1;
在方程中dis表示某一层走完的长度。
完整代码
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
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
#define REP(i,e,s) for(register int i=e; i<=s; i++)
#define DREP(i,e,s) for(register int i=e; i>=s; i--)
#define MAXN 200000+10
ll read() {
ll x=0,f=1,ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
struct edge{
ll x,y,id;
}a[MAXN];
bool cmp(edge a,edge b) {
ll as=max(a.x,a.y),bs=max(b.x,b.y);
if(as==bs) {if(a.x==b.x) return a.y>=b.y;else return a.x<b.x;}
return as<bs;
}
ll dist(ll u,ll v) {
return abs(a[u].x-a[v].x)+abs(a[u].y-a[v].y);
}
ll _right[MAXN],_left[MAXN],dis[MAXN];
ll dp[MAXN][2];
int main() {
ll n=read();
REP(i,1,n) {
a[i].x=read();
a[i].y=read();
a[i].id=max(a[i].x,a[i].y);
}
sort(a+1,a+1+n,cmp);
ll now=-1,cnt=0;
ll ans=0;
REP(i,1,n) {
if(a[i].id!=a[i-1].id) {
_right[cnt]=i-1;
dis[cnt]=dist(_right[cnt],_left[cnt]);
_left[++cnt]=i;
}
}
_right[cnt]=n;
dis[cnt]=dist(_right[cnt],_left[cnt]);
REP(i,1,cnt) {
dp[i][1]=min(dp[i-1][1]+dist(_right[i-1],_left[i]),dp[i-1][0]+dist(_left[i-1],_left[i]))+dis[i-1];
dp[i][0]=min(dp[i-1][1]+dist(_right[i-1],_right[i]),dp[i-1][0]+dist(_left[i-1],_right[i]))+dis[i-1];
}
cout<<min(dp[cnt][1],dp[cnt][0])+dis[cnt]<<endl;
return 0;
}
|
