2014
02-17

Phalanx

Today is army day, but the servicemen are busy with the phalanx for the celebration of the 60th anniversary of the PRC.
A phalanx is a matrix of size n*n, each element is a character (a~z or A~Z), standing for the military branch of the servicemen on that position.
For some special requirement it has to find out the size of the max symmetrical sub-array. And with no doubt, the Central Military Committee gave this task to ALPCs.
A symmetrical matrix is such a matrix that it is symmetrical by the “left-down to right-up” line. The element on the corresponding place should be the same. For example, here is a 3*3 symmetrical matrix:
cbx
cpb
zcc

There are several test cases in the input file. Each case starts with an integer n (0<n<=1000), followed by n lines which has n character. There won’t be any blank spaces between characters or the end of line. The input file is ended with a 0.

There are several test cases in the input file. Each case starts with an integer n (0<n<=1000), followed by n lines which has n character. There won’t be any blank spaces between characters or the end of line. The input file is ended with a 0.

3
abx
cyb
zca
4
zaba
cbab
abbc
cacq
0

3
3

zaba

cbab

abbc

cacq

i!=0&&dp[i-1][j+1]>i-a时，dp[i][j]=dp[i-1][j+1]+1

i!=0&&dp[i-1][j+1]<i-a
(其中a为从当前位置找，找到的第一个不相等的x的位置,所以i-a就为最大的对称矩阵的长度)时，dp[i][j]=i-a;

#include"stdio.h"
#include"string.h"
#define N 1001

int dp[N][N];
char s[N][N];

int main()
{
int n;
int i,j;
int a,b;
int ans;

while(scanf("%d",&n)!=-1&&n)
{
getchar();
for(i=0;i<n;i++)
gets(s[i]);

ans=0;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(i==0)dp[i][j]=1;
else
{
a=i;
b=j;
while(s[a][j]==s[i][b])
{
a--;
b++;
if(a<0||b>=n)break;
}
a=i-a;
if(a>dp[i-1][j+1])
dp[i][j]=dp[i-1][j+1]+1;
else dp[i][j]=a;
}
if(dp[i][j]>ans)ans=dp[i][j];
}
}
printf("%d\n",ans);
}
return 0;
}

1. 约瑟夫也用说这么长……很成熟的一个问题了，分治的方法解起来o(n)就可以了，有兴趣可以看看具体数学的第一章，关于约瑟夫问题推导出了一系列的结论，很漂亮