撰写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
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
InputThere 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.OutputEach test case output one line, the size of the maximum symmetrical sub- matrix.
Sample Input
3 abx cyb zca 4 zaba cbab abbc cacq 0
Sample Output
3 3
题意：给一个n*n的字母矩阵，判断是否以左下至右上为轴对称。
题解：以dp[i][j]=dp[i-1][j+1]+1||dp[i][j]=k(k为该位置上方与右方顺序字符匹配数)为递推方程解决问题，也就是以轴上的元素为基准，从上到下，从左到右得出所有的答案。另外，该dp可以滚动。
不滚：
#include<algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <cstdio>
#include <vector>
#include <string>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include <map>
using namespace std;
#define P(a,b,c) make_pair(a,make_pair(b,c))
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=n;i>=a;i--)
#define CLR(vis) memset(vis,0,sizeof(vis))
#define MST(vis,pos) memset(vis,pos,sizeof(vis))
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef pair<int,pair<int,int> >pii;
typedef long long ll;
const ll mod = 1000000007;
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
const int maxn = 1e3+5;
char m[maxn][maxn];
int dp[maxn][maxn];
int n;
int main(){
while(scanf("%d", &n)&&n){
int maxx=0;
rep(i,1,n)scanf("%s", m[i]+1);
rep(i,1,n)dp[1][i]=0;
rep(i,1,n){
rep(j,1,n){
int tx=i;
int ty=j;
int k=0;
while(tx>0&&ty<=n&&m[tx][j]==m[i][ty]){
k++,tx--,ty++;
}
if(k>dp[i-1][j+1])dp[i][j]=dp[i-1][j+1]+1;
else dp[i][j]=k;
maxx=max(maxx,dp[i][j]);
}
}
printf("%d\n", maxx);
}
}
滚：
#include<algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <cstdio>
#include <vector>
#include <string>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include <map>
using namespace std;
#define P(a,b,c) make_pair(a,make_pair(b,c))
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=n;i>=a;i--)
#define CLR(vis) memset(vis,0,sizeof(vis))
#define MST(vis,pos) memset(vis,pos,sizeof(vis))
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef pair<int,pair<int,int> >pii;
typedef long long ll;
const ll mod = 1000000007;
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
const int maxn = 1e3+5;
char m[maxn][maxn];
int dp[maxn];
int n;
int main(){
while(scanf("%d", &n)&&n){
int maxx=0;
rep(i,1,n)scanf("%s", m[i]+1);
rep(i,1,n)dp[i]=0;
rep(i,1,n){
rep(j,1,n){
int tx=i;
int ty=j;
int k=0;
while(tx>0&&ty<=n&&m[tx][j]==m[i][ty]){
k++,tx--,ty++;
}
if(k>dp[j+1])dp[j]=dp[j+1]+1;
else dp[j]=k;
maxx=max(maxx,dp[j]);
}
}
printf("%d\n", maxx);
}
}