当前位置:网站首页>HDU - 2859 Phalanx(DP)
HDU - 2859 Phalanx(DP)
2022-07-04 21:03:00 【WA_自动机】
HDU - 2859 Phalanx
Problem Description
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
Input
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.
Output
Each 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
#include<iostream>
#include<cstring>
using namespace std;
const int N = 1010;
char s[N][N];
int dp[N][N];
int main()
{
int n;
while(cin>>n,n)
{
memset(dp,0,sizeof dp);
for(int i=1;i<=n;i++) cin>>(s[i]+1);
int ans=1;
for(int i=1;i<=n;i++)
for(int j=n;j>=1;j--)
{
dp[i][j]=1;
if(i==1||j==n) continue;
int l=dp[i-1][j+1];
for(int k=1;k<=l;k++)
if(s[i-k][j]==s[i][j+k]) dp[i][j]++;
else break;
ans=max(ans,dp[i][j]);
}
cout<<ans<<endl;
}
return 0;
}
边栏推荐
- 如何使用ConcurrentLinkedQueue做一个缓存队列
- Le module minidom écrit et analyse XML
- 【LeetCode】17、电话号码的字母组合
- 淘宝商品评价api接口(item_review-获得淘宝商品评论API接口),天猫商品评论API接口
- How to implement Devops with automatic tools
- Flutter在 release版本,打开后随机白屏不显示内容
- Golang interview finishing three resumes how to write
- In the release version, the random white screen does not display the content after opening the shutter
- Jerry's ad series MIDI function description [chapter]
- [C language] deep understanding of symbols
猜你喜欢
超详细教程,一文入门Istio架构原理及实战应用
A quick start to fastdfs takes you three minutes to upload and download files to the ECS
Case sharing | integrated construction of data operation and maintenance in the financial industry
At the right time, the Guangzhou station of the city chain science and Technology Strategy Summit was successfully held
Huawei ENSP simulator configures DHCP for router
每日一题-LeetCode1200-最小绝对差-数组-排序
OMS系统实战的三两事
Master the use of auto analyze in data warehouse
迈动互联中标北京人寿保险
[public class preview]: basis and practice of video quality evaluation
随机推荐
TCP shakes hands three times and waves four times. Do you really understand?
Use of redis publish subscription
Interviewer: what is XSS attack?
Why does invariant mode improve performance
Hash table
AcWing 2022 每日一题
Arcgis 10.2.2 | arcgis license server无法启动的解决办法
Redis bloom filter
How to use concurrentlinkedqueue as a cache queue
MongoDB中的索引操作总结
redis管道
Analysis of maker education technology in the Internet Era
GTEST from ignorance to skillful use (1) GTEST installation
超详细教程,一文入门Istio架构原理及实战应用
Operation of adding material schedule in SolidWorks drawing
解析互联网时代的创客教育技术
解析steam教育中蕴含的众创空间
Jerry's ad series MIDI function description [chapter]
Flutter 返回按钮的监听
torch. Tensor and torch The difference between tensor