HDU 2589 Phalanx(dp找最大对称矩形)细节及算法详解

Phalanx

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 1220    Accepted Submission(s): 597

Problem Description Today is army day, but the servicemen are busy with the phalanx for the celebration of the 60th anniversary of the PRC.

A phalanx is a matrix of size n*n, each element is a character (a~z or A~Z), standing for the military branch of the servicemen on that position.

For some special requirement it has to find out the size of the max symmetrical sub-array. And with no doubt, the Central Military Committee gave this task to ALPCs.

A symmetrical matrix is such a matrix that it is symmetrical by the “left-down to right-up” line. The element on the corresponding place should be the same. For example, here is a 3*3 symmetrical matrix:

cbx

cpb

zcc  

Input There are several test cases in the input file. Each case starts with an integer n (0<n<=1000), followed by n lines which has n character. There won’t be any blank spaces between characters or the end of line. The input file is ended with a 0.  

Output Each test case output one line, the size of the maximum symmetrical sub- matrix.

Sample Input

3
abx
cyb
zca
4
zaba
cbab
abbc
cacq
0
        

Sample Output

3
3
        

题意：在一个大的矩阵里面，找一个以左下右上对角线对称的矩阵，其中那个对角线是任意小矩阵里面的不是那个大矩阵的对角线（一开始弄错题意，一直想不出来）

思路：如果能读懂题意，应该很容易就想出状态转移方程，每个元素左面的元素跟他右面的元素如果相同就记录就继续往下找，不相同就出循环，每次都跟左上角那个矩阵的大小相比，如果大于他就等于左上角矩阵+1（如果大了很多也只能+1，因为左上那个矩阵限制了他只能比他多1，否则就不是对称的了）；

这一题跟以往不一样，dp代表以这个点为左下角最大的矩阵边长，每次比较是跟右上角的元素比较，因为他们都在对角线上，所以在做有关矩阵题目的时候，通常可以想想在对角线上找状态转移方程；

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 1005;
int dp[maxn][maxn];
char a[maxn][maxn];
int main()
{
    int n;
    while(~scanf("%d",&n),n)
    {
        memset(dp,0,sizeof(dp));
        for(int i = 0; i < n; i++)
            scanf("%s",&a[i]);
        int ans = 1;
        for(int i = 0; i < n; i++)
            for(int j = 0; j < n ; j++)
            {
                if(i == 0 || j == n-1)    //以往我都是在前面for循环给dp赋值，看了kuangbin的博客，又学了一招
                {
                    dp[i][j] = 1;
                    continue;
                }
                int ti = i, tj = j;
                while(ti >= 0 && tj <= n - 1 && a[ti][j] == a[i][tj] )   //这里有个细节，就是如果不相同ti也已经--了，所以ti总是比相同的长度少1，所以下面可
                {                                                       //以直接i-ti，如果ti代表相同的长度应该是i-ti+1
                   ti--;
                    tj++;
                }
                ti = i - ti;
                if(dp[i-1][j+1]+1 <= ti)  dp[i][j] = dp[i-1][j+1] + 1;
                else dp[i][j] = ti;
                ans = max(ans,dp[i][j]);
            }
        printf("%d\n",ans);
    }
    return 0;
}