题意
给定一个n阶方阵，问里面最大的对阵子矩阵有多大 要求对称为从左下至右上
题解
稍稍仔细思考一下 这种问题很明显我们需要从小到大 观察一下可以知道 对一个三阶对称子矩阵，可以看出需要满足对称轴上有两个二阶对称子矩阵 同时左上与右下元素要求满足对称，那么可由二阶对称矩阵推至三阶 实际上从一阶到二阶 从三阶到四阶完全是类似的过程 由两个低一阶的对称子矩阵加上一对对称元素即可 那么用dp[i][j]表示坐标(i,j)的对称矩阵最大值，初始值设0，正好满足递推条件，逐次递推即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| #include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
char matrix[1200][1200];
int dp[1200][1200];
int main(){
int n;
while(scanf("%d",&n),n){
for(int i=0;i<n;++i){
scanf("%s",matrix[i]);
}
memset(dp,0,sizeof(dp));
int ans=0;
for(int i=1;i<n;++i){
for(int j=0;(j+i)<n;++j){
for(int t=0;(t+i)<n;++t){
if(dp[j][t+1]==(i-1)&&dp[j+1][t]==(i-1)&&matrix[j][t]==matrix[j+i][t+i]){
dp[j][t]=i;
ans=i;
}
}
}
}
printf("%d\n",ans+1);
}
return 0;
}
|