Phalanx--hdu2859（dp 最大对称子图）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2859

题意就是给你一个n*n的字符矩阵，从中选出一个最大的子矩阵（m*m）满足关于斜对角线（左下角到右上角）对称，求出这个矩阵的大小m；

我们可以用dp[i][j]表示当前位置到右上角这个子矩阵所能表示对称的矩阵最大值；

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
#define N 1100
#define INF 0xffffff

char s[N][N];
int n, dp[N][N];

int main()
{
    int n, x, y, Max;
    while(scanf("%d", &n), n)
    {
        Max=0;
        memset(s, 0, sizeof(s));
        memset(dp, 0, sizeof(dp));
        for(int i=0; i<n; i++)
            scanf("%s", s[i]);
        for(int i=0; i<n; i++)
        {
            for(int j=0; j<n; j++)
            {
                if(i==0||j==n-1)
                    dp[i][j]=1;
                x=i;y=j;
                while(x>=0&&j<n && s[x][j]==s[i][y])
                {
                    x--;
                    y++;
                }
                int m=i-x;
                if(m > dp[i-1][j+1])
                    dp[i][j] = dp[i-1][j+1] + 1;
                else
                    dp[i][j] = m;
                Max = max(Max, dp[i][j]);
            }
        }
        printf("%d
", Max);
    }
    return 0;
}