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的最大与最小值。

(这题没有讲不可能完成时怎么处理，也没有这样的数据。)

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 int a[];

 int max1[][],min1[][];

 int n,m,k,s,ans;

 int main()

 {

     int i,j,t;

     scanf("%d%d%d%d",&n,&m,&k,&s);

     memset(min1,0x3f,sizeof(min1));

     memset(max1,,sizeof(max1));

     for(i=;i<=n;i++)

         for(j=;j<=m;j++)

         {

             scanf("%d",&t);

             max1[t][]=max(max1[t][],i+j);

             max1[t][]=max(max1[t][],i-j);

             max1[t][]=max(max1[t][],-i+j);

             max1[t][]=max(max1[t][],-i-j);

             min1[t][]=min(min1[t][],i+j);

             min1[t][]=min(min1[t][],i-j);

             min1[t][]=min(min1[t][],-i+j);

             min1[t][]=min(min1[t][],-i-j);

         }

     scanf("%d",&a[]);

     for(i=;i<=s;i++)

     {

         scanf("%d",&a[i]);

         for(j=;j<=;j++)

             ans=max(ans,max(max1[a[i-]][j]-min1[a[i]][j],max1[a[i]][j]-min1[a[i-]][j]));

     }

     printf("%d",ans);

     return ;

 }