题意:找元素关于 left-down to right-up 对称的最大矩阵
分析:有两条对角线,我们可以转化为常用的那条对角线来求,就像在一张纸上写上东西,把纸反过来从背面看的效果是一样的。每个点向两边扩展,如果能扩展完,num【x】【y】=num【x-1】【y-1】+1;不能的话,中途停止了,就等于当前所能扩展的行数。
//只要打出num矩阵,然后结合代码,就很好理解动态规划的过程了
code:
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<algorithm>
#include<iostream>
#include<set>
#include<iomanip>
using namespace std;
int n,m,k;
int mmax;
int a[111111];
char tu[1130][1120];
int num[1120][1120];
void dp1(int x,int y)
{
int i;
int v = num[x-1][y-1];
for(i=1;i<=v;i++)
{
if(tu[x-i][y]!=tu[x][y-i])
break;
}
if(i>v)num[x][y] = num[x-1][y-1]+1;
else num[x][y] = i;
if(mmax<num[x][y])
mmax =num[x][y] ;
}
int main()
{
while(cin>>n)
{
if(n==0)break;
memset(num,0,sizeof(num));
for(int i=n;i>=1;i--)//转换对角线方向
{
scanf("%s",&tu[i][1]);
}
mmax = 0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
dp1(i,j);
}
}
// for(int i=1;i<=n;i++)
// {
// for(int j=1;j<=n;j++)
// {
// printf("%d ",num[i][j]);
// }
// printf("\n");
// }
cout<<mmax<<endl;
}
return 0;
}