hdu 4618 Palindrome Sub-Array

http://acm.hdu.edu.cn/showproblem.php?pid=4618
直接DP+メモリ化
時間の複雑さは300^4と見られますが、実際に実行すると、この値よりはるかに小さいです。
コード:

#include<iostream>

#include<cstdio>

#include<string>

#include<cstring>

#include<cmath>

#include<set>

#include<map>

#include<stack>

#include<vector>

#include<algorithm>

#include<queue>

#include<bitset>

#include<deque>

#include<numeric>



//#pragma comment(linker, "/STACK:1024000000,1024000000")



using namespace std;



typedef long long ll;

typedef unsigned int uint;

typedef pair<int,int> pp;

const double eps=1e-9;

const int INF=0x3f3f3f3f;

const ll MOD=1000000007;

const int N=301;

int a[N][N];

char dp[N][N][N];

char dfs(int x,int y,int p)

{

    if(dp[x][y][p]!=-1)

    return dp[x][y][p];

    if(p==1||p==0)

    return (dp[x][y][p]=1);

    for(int i=0;i<p;++i)

    {

        if(a[x][y+i]!=a[x+p-1][y+i]||a[x+i][y]!=a[x+i][y+p-1])

        return (dp[x][y][p]=0);

    }

    if(dfs(x+1,y+1,p-2)==0)

    return (dp[x][y][p]=0);

    return (dp[x][y][p]=1);

}

int main()

{

    //freopen("data.in","r",stdin);

    int T;

    scanf("%d",&T);

    while(T--)

    {

        int n,m;

        scanf("%d %d",&n,&m);

        memset(a,0,sizeof(a));

        for(int i=1;i<=n;++i)

        for(int j=1;j<=m;++j)

        scanf("%d",&a[i][j]);

        int ans=0;

        memset(dp,-1,sizeof(dp));

        for(int i=1;i<=n;++i)

        for(int j=1;j<=m;++j)

        for(int l=1;l<=min(n,m);++l)

        if(n-i+1>=l&&m-j+1>=l&&l>ans)

        {

            if(dfs(i,j,l)==1)

            ans=max(ans,l);

        }

        printf("%d
",ans);

    }

    return 0;

}