对称矩阵 DP——hdu 2859

3

abx

cyb

zca

转化---->

1 1 1

2 2 1

3 2 1

i :1->n

j:1->n

dp[i][j]=min(dp[i][j],dp[i-1][j+1]);

#include<stdio.h>

char map[1009][1009];
int a[1009][1009];

int min(int a,int b)
{
    if(a>b)return b;
    else return a;
}
        
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        if(n==0)return 0;

        int i,j,k;
        
        for(i=1;i<=n;i++)
        {
            scanf("%s",&map[i][1]);
            for(j=1;j<=n;j++)
            {
                a[i][j]=1;
            }
        }

        for(i=1;i<=n;i++)
        {
            for(j=1;j<=n;j++)
            {
                for(k=1;;k++)
                {
                    if(i-k<=0||j+k>n)
                    {
                        break;
                    }
                    if(map[i-k][j]!=map[i][j+k])
                        break;
                }

                a[i][j]=k;
            }
        }

        for(i=1;i<=n;i++)
        {
            for(j=1;j<=n;j++)
            {
                if(i-1>=1&&j+1<=n)
                {
                    a[i][j]=min(a[i][j],a[i-1][j+1]+1);
                }
            }
        }

        int max=1;
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=n;j++)
            {
                if(max<a[i][j])
                    max=a[i][j];
            }
        }

        printf("%d\n",max);
    }
}