【HDU - 2859 】Phalanx （dp 最大对称子图）
Sky丨Star 人气:1Phalanx
先搬翻译
Descriptions:
给你一个矩阵，只由小写或大写字母构成。求出它的最大对称子矩阵的边长。
其中对称矩阵是一个k*k的矩阵，它的元素关于从左下角到右上角的对角线对称。
例如下面这个3* 3的矩阵是对称矩阵：
cbx
cpb
zcc
例如下面这个3* 3的矩阵是对称矩阵：
cbx
cpb
zcc
Input
多组数据。每一组第一行是一个 n (0<n<=1000),下面是n行，每一行有n个字母，中间没有空格。数据以n=0结束。
Output
每组数据输出最大的对称矩阵的边长。
Sample Input
3 abx cyb zca 4 zaba cbab abbc cacq 0
Sample Output
3 3
题目链接：
https://vjudge.net/problem/HDU-2859
dp[i][j] 表明的是你在第i行第j列的时候的最大对称矩阵
dp[i][j]可以在满足条件的情况下转移到dp[i-1][j+1]的状态上来
AC代码
#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#define Mod 1000000007
#define eps 1e-6
#define ll long long
#define INF 0x3f3f3f3f
#define MEM(x, y) memset(x, y, sizeof(x))
#define Maxn 1000+10
using namespace std;
int n,len,ans;
char s[Maxn][Maxn];//存图像
int dp[Maxn][Maxn];//在第i行第j列的时候的最大对称矩阵
int main()
{
while(cin>>n&&n!=0)
{
ans=1;//初始化
MEM(s,0);
MEM(dp,0);
for(int i=0; i<n; i++)//存图形
for(int j=0; j<n; j++)
cin>>s[i][j];
for(int i=0; i<n; i++)//开始一个一个为顶点开始搜索
{
for(int j=n-1; j>=0; j--)
{
dp[i][j]=1;//每一个字母 其本身就是一个对称矩阵
if(i==0||j==n-1)//边缘部分不用管
continue;
int t=dp[i-1][j+1];//其右上角那个点是t阶
//检测这个点是否能超过右上角的对称矩阵
for(int k=1; k<=t; k++)
{
if(s[i-k][j]==s[i][k+j])
dp[i][j]++;
else
break;
}
ans=max(ans,dp[i][j]);
}
}
cout<<ans<<endl;
}
return 0;
}
加载全部内容