HDU - 2859 Phalanx （dp_最大对称子图）

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

题意：

求最大对称子图（关于反对角线对称）

dp[ i ][ j ] 表示以 (i, j) 为左下角的最大对称子图，必须包含该点

每次向上向下查找最大匹配数，如果大于右上角的dp值，那么就是右上角的dp值 + 1，因为如果再多的话内一层会不再匹配。

如果小于右上角的dp值，那么就是该点的最大匹配数，因为如果再多的话外层会不再匹配

左边是第一种情况，右边是第二种情况，红色框表示该点的最大对称子图

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const ll mod = 1e9 + 7;
const double eps = 1e-8;
const int N = 1e3 + 10;

int dp[N][N];   ///dp[i][j]：以(i, j)为左下角的最大对称矩阵，必须包括(i, j)
char s[N][N];

int main()
{
    int n;
    while(~scanf("%d", &n) && n)
    {
        for(int i = 1; i <= n; ++i)
        {
            scanf("%s", s[i] + 1);
        }
        int maxx = 0;
        for(int i = 1; i <= n; ++i)
        {
            for(int j = 1; j <= n; ++j)
            {
                if(i == 1 || j == n)    ///每个字母都算一个
                {
                    dp[i][j] = 1;
                }
                int x = i;
                int y = j;
                while(x >= 1 && y <= n && s[x][j] == s[i][y])   ///从(i, j)向上向右找最大匹配的数量
                {
                    x--;
                    y++;
                }
                int cnt = i - x;    ///最大匹配数量
                if(cnt > dp[i - 1][j + 1])              ///超过了以(i - 1, j + 1)为左下角的最大对称矩阵
                {
                    dp[i][j] = dp[i - 1][j + 1] + 1;    ///最多也就延伸到dp[i - 1][j + 1] + 1;（向左下方扩展了一行）
                }
                else
                {
                    dp[i][j] = cnt;
                }
                maxx = max(maxx, dp[i][j]);
            }
        }
        cout<<maxx<<'\n';
    }
    return 0;
}