hdu 2859 Phalanx

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

题目坑爹啊！原来以为要O（n^2）才能过，没想到是n^3的复杂度，10^9方的题都可以出，太没天理了。。。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<string>
#include<queue>
#include<algorithm>
#include<vector>
#include<stack>
#include<list>
#include<iostream>
#include<map>
using namespace std;
#define inf 0x3f3f3f3f
#define Max 110
int max(int a,int b)
{
	return a>b?a:b;
}
int min(int a,int b)
{
	return a<b?a:b;
}
int n;
char mp[1010][1010];
int dp[1010][1010];
int main()
{
    int i,j,k;
    while(scanf("%d",&n),n)
    {
        for(i=0;i<n;i++)
            scanf("%s",mp[i]);
        memset(dp,0,sizeof(dp));
        for(i=0;i<n;i++)
            for(j=0;j<n;j++)
            {
              //  int flag=0;
                for(k=1;j-k>=0&&i+k<n;k++)
                {
                    if(mp[i][j-k]!=mp[i+k][j])
                    {
                        break;
                    }
                }
                dp[i][j]=j-k+1;

            }
        int ans=1;
        for(k=0;k<n;k++)
            for(j=1;j<=k;j++)
            {
                i=k-j;
                dp[i][j]=max(dp[i][j],dp[i+1][j-1]);
                ans=max(ans,j-dp[i][j]+1);
            }
        for(k=n;k<2*n-1;k++)
            for(i=n-2;i>=k-n+1;i--)
            {
                j=k-i;
                dp[i][j]=max(dp[i][j],dp[i+1][j-1]);
                ans=max(ans,j-dp[i][j]+1);
            }
        printf("%d\n",ans);
    }
}