P2060 [HNOI2006]马步距离

数据到百万级别，明显爆搜不行，剪枝也没法剪。先打表。发现小数据内步数比较受位置关系影响，但数据一大就不影响了。大概搜了一个20*20的表把赋值语句打出来。判断时贪心，看两点间位置差，根据x差或者y差的大小比较来采取两种不同跳法，直到在小范围内再直接借助打的表加以输出。注意起点和目标的位置的及时调整（依据对称性，见line49），方便跳动。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<algorithm>
 6 #define dbg(x) cerr<<#x<<" = "<<x<<endl
 7 #define ddbg(x,y) cerr<<#x<<" = "<<x<<"   "<<#y<<" = "<<y<<endl
 8 using namespace std;
 9 typedef long long ll;
10 template<typename T>inline char MIN(T&A,T B){return A>B?A=B,1:0;}
11 template<typename T>inline char MAX(T&A,T B){return A<B?A=B,1:0;}
12 template<typename T>inline T _min(T A,T B){return A<B?A:B;}
13 template<typename T>inline T _max(T A,T B){return A>B?A:B;}
14 template<typename T>inline T read(T&x){
15     x=0;int f=0;char c;while(!isdigit(c=getchar()))if(c=='-')f=1;
16     while(isdigit(c))x=x*10+(c&15),c=getchar();return f?x=-x:x;
17 }
18 const int N=21;
19 int step[N][N]={{0,3,2,3,2,3,4,5,4,5,6,7,6,7,8,9,8,9,10,11,10},
20                 {3,2,1,2,3,4,3,4,5,6,5,6,7,8,7,8,9,10,9,10,11},
21                 {2,1,4,3,2,3,4,5,4,5,6,7,6,7,8,9,8,9,10,11,10},
22                 {3,2,3,2,3,4,3,4,5,6,5,6,7,8,7,8,9,10,9,10,11},
23                 {2,3,2,3,4,3,4,5,4,5,6,7,6,7,8,9,8,9,10,11,10},
24                 {3,4,3,4,3,4,5,4,5,6,5,6,7,8,7,8,9,10,9,10,11},
25                 {4,3,4,3,4,5,4,5,6,5,6,7,6,7,8,9,8,9,10,11,10},
26                 {5,4,5,4,5,4,5,6,5,6,7,6,7,8,7,8,9,10,9,10,11},
27                 {4,5,4,5,4,5,6,5,6,7,6,7,8,7,8,9,8,9,10,11,10},
28                 {5,6,5,6,5,6,5,6,7,6,7,8,7,8,9,8,9,10,9,10,11},
29                 {6,5,6,5,6,5,6,7,6,7,8,7,8,9,8,9,10,9,10,11,10},
30                 {7,6,7,6,7,6,7,6,7,8,7,8,9,8,9,10,9,10,11,10,11},
31                 {6,7,6,7,6,7,6,7,8,7,8,9,8,9,10,9,10,11,10,11,12},
32                 {7,8,7,8,7,8,7,8,7,8,9,8,9,10,9,10,11,10,11,12,11},
33                 {8,7,8,7,8,7,8,7,8,9,8,9,10,9,10,11,10,11,12,11,12},
34                 {9,8,9,8,9,8,9,8,9,8,9,10,9,10,11,10,11,12,11,12,13},
35                 {8,9,8,9,8,9,8,9,8,9,10,9,10,11,10,11,12,11,12,13,12},
36                 {9,10,9,10,9,10,9,10,9,10,9,10,11,10,11,12,11,12,13,12,13},
37                 {10,9,10,9,10,9,10,9,10,9,10,11,10,11,12,11,12,13,12,13,14},
38                 {11,10,11,10,11,10,11,10,11,10,11,10,11,12,11,12,13,12,13,14,13},
39                 {10,11,10,11,10,11,10,11,10,11,10,11,12,11,12,13,12,13,14,13,14}};
40 inline void swap(int&x,int&y){x^=y^=x^=y;}
41 
42 int main(){//freopen("test.in","r",stdin);freopen("test.out","w",stdout);
43     int sx,sy,tx,ty,ans=0;
44     read(sx),read(sy),read(tx),read(ty);
45     if(sx>tx)swap(sx,tx);if(sy>ty)swap(sy,ty);
46     while(tx-sx>=N||ty-sy>=N){//ddbg(sx,sy);
47         if(ty-sy<tx-sx)sx+=2,++sy;
48         else ++sx,sy+=2;++ans;
49         if(sx>tx)swap(sx,tx);if(sy>ty)swap(sy,ty);
50     }
51     return printf("%d",ans+step[tx-sx][ty-sy]),0;
52 }