HDU2859 Phalanx （动态规划）-白红宇

HDU2859 Phalanx （动态规划）

阅读量：4582 次

发布时间：2019-06-09

本文共 1655 字，大约阅读时间需要 5 分钟。

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

InputThere 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.OutputEach test case output one line, the size of the maximum symmetrical sub- matrix.

Sample Input

3abxcybzca4zabacbababbccacq0

Sample Output

33 题意： 问最大对称矩阵，对称轴是这样的：/ 思路： dp[i][j]表示以i,j为左下角坐标的最大矩阵大小。 更新的时候向上和向右走就行了，只是感觉这个复杂度不太正常。

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #define fuck(x) cout<<#x<<" = "<
                 
                  <
                  
                   n){ break;} if(mp[t1][j]==mp[i][t2]){rec++;} else break; } dp[i][j]=1; if(rec>dp[i-1][j+1]){dp[i][j]=dp[i-1][j+1]+1;ans=max(ans,dp[i][j]);} else dp[i][j]=rec; } } printf("%d\n",ans); } return 0;}

View Code

转载于:https://www.cnblogs.com/ZGQblogs/p/10664506.html

你可能感兴趣的文章