Hdu 2859 - Phalanx (基础dp)

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

题目大意：
给定一个字符方阵，求最大的一个子方阵的大小，使得其以副对角线为轴完全对称

分析：
直接从上至下$O(n^2)$遍历，对$dp[i][j]$，查看位置$(i,j)$上方和右方的总匹配数$cnt$（不包括自身），若大于$dp[i-1][j-1]$，则$dp[i][j]$更新为$dp[i-1][j-1]+1$，否则$dp[i][j] = cnt+1$

实际上一开始想到的就是这种做法，但是估算复杂度是$O(n^3)$，$1\leq n \leq 1000$ ，大约1e9的复杂度，所以一开始估计过不了，就没继续想，后来看题解才发现这题是5s的题，1e9绰绰有余，实在应该再仔细点的

代码：

#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<string.h>
#include<math.h>
using namespace std;

typedef long long ll;

const int maxn = 1200;

int n;
char mat[maxn][maxn];
int dp[maxn][maxn];

int main()
{
    while (~scanf("%d",&n)&&n)
    {
        memset(dp,0,sizeof(dp));
        for (int i = 1 ; i <= n ; i ++)
        {
            scanf("%s",mat[i]+1);
        }
        int maxx = 1;
        for (int i = 1 ; i <=n ; ++i)
        {
            for (int j = 1 ; j <= n ; j ++)
            {
                if (i==1||j==n)
                {
                    dp[i][j] = 1;
                    continue;
                }
                int cnt = 0;
                for (int k = 1 ; k +j<=n && i - k>=1 ; k ++)
                {
                    if (mat[i-k][j]==mat[i][j+k])
                        cnt++;
                    else
                        break;
                }
                if (cnt>=dp[i-1][j+1])
                    dp[i][j] = dp[i-1][j+1]+1;
                else
                    dp[i][j] = cnt+1;
                maxx = max(dp[i][j],maxx);
            }
        }
        printf("%d\n",maxx);
    }

    return 0;
}