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;
}