Phalanx [kuangbin带你飞]刷题记录

Phalanx

题目链接

核心思想 :

dp
我们可以观察出一个结论 : 以点(i,j)为左下角的边长为k对称矩阵那么以点(i-1,j+1)为左下标边长为k-1的矩阵一定对称 , 而我们只有推出了点(i-1,j+1)为左下标边长为k-1的矩阵是对称矩阵那么就只需要检查下边和左边就知道点(i,j)为左下角的边长为k对称矩阵是否存在了

AC代码

#include<iostream>
#include<queue>
#include<string>
#include<string.h>
#include<algorithm>
#include<cstdio>
#include<map>
#include<set>
#include<stack>
#include<vector>
#include<cmath>
using namespace std;
typedef long long ll;
#define repi(x,y,z) for(int x = y; x<=z;++x)
#define deci(x,y,z) for(int x = y; x>=z;--x)
#define repl(x,y,z) for(ll x = y; x<=z;++x)
#define decl(x,y,z) for(ll x = y; x>=z;--x)
#define gcd(a, b) __gcd(a, b)
#define lcm(a, b) (a * b / gcd(a, b))
#define INF 0x3f3f3f3f
#define ms(a,b) memset( a, b , sizeof (a) )
#define txt intxt()
#define CAS int cas;cin>>cas;while(cas--)
#define py  puts("YES")
#define pn  puts("NO")
#define pcn  putchar('\n')
inline void intxt( ){#ifndef ONLINE_JUDGEfreopen("in.txt","r",stdin);#endif
}
inline int read( ){int f = 1,x = 0;char ch = getchar();while (ch < '0' || ch > '9')   {if (ch == '-') f = -1; ch = getchar();}while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}x *= f;return x;
}
const int maxn=1e3+5;int n;
int dp[maxn][maxn];
char s[maxn][maxn];int main(){txt;while( 1 ){n=read();if(n==0) break;repi(i,1,n){scanf("%s",s[i]+1);}repi(i,1,n){repi(j,1,n){dp[i][j]=1;//初始化}}int ans=1;repi(i,1,n){deci(j,n,1){int k=dp[i][j];if( j-1<=0 || i+1>n ) continue;repi(id,1,k){if( s[i-id+1][j-1]==s[i+1][j+id-1] ){//检查左边和下边是否相等dp[i+1][j-1]++;}else{break;}}ans=max( dp[ i+1 ][j-1],ans );}}cout<<ans<<endl;}return 0;
}