Q - Phalanx

 HDU - 2859 

给你一个矩阵，只由小写或大写字母构成。求出它的最大对称子矩阵的边长。

其中对称矩阵是一个k*k的矩阵，它的元素关于从左下角到右上角的对角线对称。 
例如下面这个3* 3的矩阵是对称矩阵： 
cbx 
cpb 
zcc

Input

多组数据。每一组第一行是一个 n (0<n<=1000),下面是n行，每一行有n个字母，中间没有空格。数据以n=0结束。

Output

每组数据输出最大的对称矩阵的边长。

Sample Input

3
abx
cyb
zca
4
zaba
cbab
abbc
cacq
0

Sample Output

3
3

题解：找一下从当前位置往上和往左最长的的对称长度，与上一个状态+1相比的最小值

#include <iostream>
#include <stdio.h>
#include <cstring>
using namespace std;
const long long mod = 1e9+7;
typedef long long int ll;
#define maxn 2000+5
#define INF 0x3f3f3f3f
#define LLF 0x7fffffffffffffff
char a[maxn][maxn];
int dp[maxn][maxn];
int main(){
    // #ifndef ONLINE_JUDGE    //if not define 如果没有定义这个的话就执行下面
	// freopen("input.in", "r", stdin);   //只改变输入流的文件指针，读入这个文件的内容（必须要有input这个文件）stdin是标准输入流的文件指针
	// freopen("output1.out", "w", stdout);  //只改变输出流的文件指针，写入output内（如果没有output这个文件就会自动生成）stdout是标准输出流的文件指针
	// #endif
    int n;
    while(scanf("%d",&n)&&n){
        for(int i=1;i<=n;i++){
            scanf("%s",a[i]+1);    
        }
        int ans=1;
        for(int i=1;i<=n;i++){
            for(int j=n;j>=1;j--){
                if(i==1||j==n){
                    dp[i][j]=1;
                    continue;
                }
                int x=i-1,y=j+1;
                while(a[x][j]==a[i][y]&&x>=1&&y<=n)x--,y++;
                int tmp=i-x;
                dp[i][j]=min(tmp,dp[i-1][j+1]+1);
                ans=max(dp[i][j],ans);
            }
            
        }
        cout<<ans<<endl;
    }

}