[某人的題解]徒步旅行（travel）

題目描述

小 A 決定開始一場奇妙的徒步旅行，旅行地圖可以看成是一個平面直角坐標系，小 A 從家 O ( 0 , 0 ) O(0, 0) O(0,0)出發，每一步移動只能由他此時所在的位置 ( x , y ) (x,y) (x,y)走到以下四個坐標之一： ( x ? 1 , y ) , ( x , y ? 1 ) , ( x + 1 , y ) , ( x , y + 1 ) (x-1,y),(x,y-1),(x+1,y),(x,y+1) (x?1,y),(x,y?1),(x+1,y),(x,y+1)，

現在有 n n n個旅游景點，第 i i i個旅游景點位置為(x_i ,y_i)，

由于世界如此之大，整個旅行地圖被分成了多個不同的氣候區，某個景點(x_i ,y_i)的氣候區C_i=max(x_i ,y_i) ，小 A 想要更好的了解這個世界使得他這次徒步旅行更有意義，所以他想要去氣候區 旅行當且僅當訪問完氣候區為 的所有旅游景點，當他訪問完所有的景點時，他會回到家里，

輸入格式

小 A 想讓你幫他設計出一條旅游路線使得他移動的步數最少，因為徒步旅行還是比較累的……
輸入格式
第一行輸入一個整數n，表示旅游景點數量，
接下來n行，每行一個整數對(x_i ,y_i)代表第 個景區的位置，

輸出格式

僅一行，表示小 A 完成旅行所需移動的最少步數，

樣例

樣例輸入1

8
2 2
1 4
2 3
3 1
3 4
1 1
4 3
1 2

樣例輸出1

20

樣例輸入2

5
2 1
1 0
2 0
3 2
0 3

樣例輸出2

12

分析

首先看到這一道題，一定會想到使用搜索（他把方向都告訴你了），
但我看了一眼資料—— 1 0 9 10^9 109，（我TM直接放棄 ）
所以說搜索是肯定會超時的，但終究有點分，
對于每一個氣候，可以發現它的起點和終點最有的取法一定是兩個端點，
在最優解中，只需要走到兩個端點，就可以遍歷玩這一氣候區的所有點，

然后……
先把輸入的 x , y x,y x,y按氣候區的從小到大排序，即：

bool cmp(Node x, Node y) {
	return x.Map_C != y.Map_C ? x.Map_C < y.Map_C : (x.Map_X != y.Map_X ? x.Map_X < y.Map_X : x.Map_Y < y.Map_Y); 
}

我們用兩個dp來存盤，一個存貯最左端點，一個存盤最右端點，
所以
d p 1 [ i ] = m i n ( d p 1 [ i ? 1 ] + c a l c ( l [ i ? 1 ] , r [ i ] ) , d p 2 [ i ? 1 ] + c a l c ( r [ i ? 1 ] , r [ i ] ) ) + c a l c ( r [ i ] , l [ i ] ) ; dp1[i] = min(dp1[i - 1] + calc(l[i - 1], r[i]), dp2[i - 1] + calc(r[i - 1], r[i])) + calc(r[i], l[i]); dp1[i]=min(dp1[i?1]+calc(l[i?1],r[i]),dp2[i?1]+calc(r[i?1],r[i]))+calc(r[i],l[i]);
d p 2 [ i ] = m i n ( d p 1 [ i ? 1 ] + c a l c ( l [ i ? 1 ] , l [ i ] ) , d p 2 [ i ? 1 ] + c a l c ( r [ i ? 1 ] , l [ i ] ) ) + c a l c ( l [ i ] , r [ i ] ) ; dp2[i] = min(dp1[i - 1] + calc(l[i - 1], l[i]), dp2[i - 1] + calc(r[i - 1], l[i])) + calc(l[i], r[i]); dp2[i]=min(dp1[i?1]+calc(l[i?1],l[i]),dp2[i?1]+calc(r[i?1],l[i]))+calc(l[i],r[i]);
l [ i ] l[i] l[i]用于記錄最左端點的排序后順序， r [ i ] r[i] r[i]用于記錄最右端點的排序后順序，calc函式是用來計算兩點間距離的，不難想到：

long long calc(long long x, long long y) {
	return abs(a[x].Map_X - a[y].Map_X) + abs(a[x].Map_Y - a[y].Map_Y);
}

（注：記得將氣候區離散化，否則會超時）

代碼實作

綜上所述，代碼就出來了

#include <map>
#include <set>
#include <cstdio>
#include <algorithm>
using namespace std;
#define ll long long
const ll MAXN = 3e5 + 5;
struct Node {
	ll Map_X, Map_Y, Map_C;
};
set<ll> st;
map<ll, ll> mpl;
map<ll, ll> mpr;
map<ll, ll> id1;
map<ll, ll> id2;
map<ll, bool> mpX;
map<ll, bool> mpY;
Node a[MAXN];
ll dp1[MAXN], dp2[MAXN];
ll l[MAXN], r[MAXN];
ll n;
bool cmp(Node x, Node y) {
	return x.Map_C != y.Map_C ? x.Map_C < y.Map_C : (x.Map_X != y.Map_X ? x.Map_X < y.Map_X : x.Map_Y < y.Map_Y); 
}
ll calc(ll x, ll y) {
	return abs(a[x].Map_X - a[y].Map_X) + abs(a[x].Map_Y - a[y].Map_Y);
}
void Read() {
	scanf("%lld", &n);
	mpX[0] = mpY[0] = 1;
	for(ll i = 1; i <= n; i++) {
		scanf("%lld %lld", &a[i].Map_X, &a[i].Map_Y);
		a[i].Map_C = max(a[i].Map_X, a[i].Map_Y);
		st.insert(a[i].Map_C);
	}
	for(set<ll>::iterator it = st.begin(); it != st.end(); it++) {
		mpl[*it] = 0x7fffffff;
	}
	sort(a + 1, a + 1 + n, cmp);
	for(ll i = 1; i <= n; i++) {
		if(min(a[i].Map_X, a[i].Map_Y) <= mpl[a[i].Map_C]) {
			mpl[a[i].Map_C] = min(mpl[a[i].Map_C], min(a[i].Map_X, a[i].Map_Y));
			id2[a[i].Map_C] = i;
		}
		if(min(a[i].Map_X, a[i].Map_Y) >= mpr[a[i].Map_C]) {
			mpr[a[i].Map_C] = max(mpr[a[i].Map_C], min(a[i].Map_X, a[i].Map_Y));
			id1[a[i].Map_C] = i;
		}
	}
	int p = 0;
	for(set<ll>::iterator it = st.begin(); it != st.end(); it++) {
		l[++p] = id2[*it];
		r[p] = id1[*it];
	}
	for(ll i = 1; i <= p; i++) {
        dp1[i] = min(dp1[i - 1] + calc(l[i - 1], r[i]), dp2[i - 1] + calc(r[i - 1], r[i])) + calc(r[i], l[i]);
        dp2[i] = min(dp1[i - 1] + calc(l[i - 1], l[i]), dp2[i - 1] + calc(r[i - 1], l[i])) + calc(l[i], r[i]);
	}
	printf("%lld", min(dp1[p] + calc(l[p], 0), dp2[p] + calc(r[p], 0)));
}
int main() {
	Read();
	return 0;
}

可能有億點點麻煩，真就億點點唄，（小聲）