Dima and Magic Guitar CodeForces - 366E

Dima and Magic Guitar CodeForces - 366E

題意：

http://blog.csdn.net/u011026968/article/details/38716425
http://vawait.com/2013/11/codeforces-366e/
http://www.cnblogs.com/jianglangcaijin/archive/2013/11/25/3441319.html

對於s中任意相鄰兩個數x和y，都要求在矩形中找出任意兩個分別等於x和y的點，然後求其曼哈頓距離，本題要求所有求出的曼哈頓距離的最大值最大。容易想到，應當是讓一對點的曼哈頓距離最大，其他點任意即可。也就是對於s中所有相鄰兩個數，找出矩形中分別等於這兩個數且之間曼哈頓距離最大的兩個點。

曼哈頓距離等於以下的最大值：

(xa-xb)+(ya-yb)
(xa-xb)-(ya-yb)
-(xa-xb)+(ya+yb)
-(xa-xb)-(ya-yb)

也就是這些的最大值：

(xa+ya)-(xb+yb)
(xa-ya)-(xb-yb)
(-xa+ya)-(-xb+yb)
(-xa-ya)-(-xb-yb)

因此要求值分別為a和b的點間最大的曼哈頓距離，就是這四種的最大值，而每種的最大值都是被減數最大，減數最小。也就是分別記錄所有值為a的點中xa+ta,xa-ya,-xa+ya,-xa-ya的最大與最小值。

(這題沒有講不可能完成時怎麼處理，也沒有這樣的數據。)

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 int a[100110];
 6 int max1[11][4],min1[11][4];
 7 int n,m,k,s,ans;
 8 int main()
 9 {
10     int i,j,t;
11     scanf("%d%d%d%d",&n,&m,&k,&s);
12     memset(min1,0x3f,sizeof(min1));
13     memset(max1,140,sizeof(max1));
14     for(i=1;i<=n;i++)
15         for(j=1;j<=m;j++)
16         {
17             scanf("%d",&t);
18             max1[t][0]=max(max1[t][0],i+j);
19             max1[t][1]=max(max1[t][1],i-j);
20             max1[t][2]=max(max1[t][2],-i+j);
21             max1[t][3]=max(max1[t][3],-i-j);
22             min1[t][0]=min(min1[t][0],i+j);
23             min1[t][1]=min(min1[t][1],i-j);
24             min1[t][2]=min(min1[t][2],-i+j);
25             min1[t][3]=min(min1[t][3],-i-j);
26         }
27     scanf("%d",&a[1]);
28     for(i=2;i<=s;i++)
29     {
30         scanf("%d",&a[i]);
31         for(j=0;j<=3;j++)
32             ans=max(ans,max(max1[a[i-1]][j]-min1[a[i]][j],max1[a[i]][j]-min1[a[i-1]][j]));
33     }
34     printf("%d",ans);
35     return 0;
36 }