当前位置:网站首页>HDU - 2859 Phalanx(DP)
HDU - 2859 Phalanx(DP)
2022-07-04 21:50:00 【WA_ automata】
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;
}
边栏推荐
- TCP shakes hands three times and waves four times. Do you really understand?
- Daily question-leetcode556-next larger element iii-string-double pointer-next_ permutation
- Daily question -leetcode1200- minimum absolute difference - array - sort
- CloudCompare&Open3D DBSCAN聚类(非插件式)
- Flutter WebView示例
- 旋变串判断
- [wechat applet] collaborative work and release
- Liu Jincheng won the 2022 China e-commerce industry innovation Figure Award
- Use of redis publish subscription
- Day24: file system
猜你喜欢
MongoDB聚合操作总结
[C language] deep understanding of symbols
How to remove the black dot in front of the title in word document
【活动早知道】LiveVideoStack近期活动一览
QT—双缓冲绘图
Sorting and sharing of selected papers, systems and applications related to the most comprehensive mixed expert (MOE) model in history
el-tree结合el-table,树形添加修改操作
Day24: file system
奋斗正当时,城链科技战略峰会广州站圆满召开
[leetcode] 17. Letter combination of telephone number
随机推荐
[public class preview]: basis and practice of video quality evaluation
Jerry's ad series MIDI function description [chapter]
MP3是如何诞生的?
Golang面试整理 三 简历如何书写
Redis 排查大 key 的3种方法,优化必备
【C语言】符号的深度理解
IIC (STM32)
2022 version of stronger jsonpath compatibility and performance test (snack3, fastjson2, jayway.jsonpath)
How to use concurrentlinkedqueue as a cache queue
Application practice | Shuhai supply chain construction of data center based on Apache Doris
HDU - 1078 FatMouse and Cheese(记忆化搜索DP)
Sorting and sharing of selected papers, systems and applications related to the most comprehensive mixed expert (MOE) model in history
Hash table
【活动早知道】LiveVideoStack近期活动一览
Redis pipeline
Exclusive interview of open source summer | new committer Xie Qijun of Apache iotdb community
每日一题-LeetCode1200-最小绝对差-数组-排序
Flutter WebView示例
CloudCompare&Open3D DBSCAN聚类(非插件式)
HDU - 2859 Phalanx(DP)