傳送門：http://acm.hdu.edu.cn/showproblem.php?pid=2859

解題思路：

對于每個(gè)字符看該列以上和該行右側(cè)的字符匹配量，如果匹配量大于右上角記錄下來的矩陣大小，就是右上角的數(shù)值+1，否則就是這個(gè)匹配量。

實(shí)現(xiàn)代碼：

#include <cstdio> #include <algorithm> #include <iostream> #include <cstring> using namespace std;const int MAXN=1010; int dp[MAXN][MAXN]; char ch[MAXN][MAXN];int main(){int N;while(scanf("%d",&N)&&N){for(int i=0;i<N;i++)scanf("%s",ch[i]);int ans=1;memset(dp,0,sizeof(dp));for(int i=0;i<N;i++)for(int j=0;j<N;j++){if(i==0||j==N-1){dp[i][j]=1;continue;}int t1=i,t2=j;while(t1>=0&&t2<N&&ch[t1][j]==ch[i][t2]){t1--;t2++;}t1=i-t1;if(t1>=dp[i-1][j+1]+1)dp[i][j]=dp[i-1][j+1]+1;elsedp[i][j]=t1;ans=max(ans,dp[i][j]);}cout<<ans<<endl;}return 0; }

下面的超時(shí)：

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std;const int MAXN=1000; const int INF=1<<30; int dp[MAXN][MAXN]; char ch[MAXN][MAXN]; /* dp[i][j]表示以a[i][j]為左下角的對稱矩陣的大小; */int main(){int N;while(scanf("%d",&N)!=EOF&&N){for(int i=0;i<N;i++)scanf("%s",ch[i]);for(int i=0;i<N;i++)dp[0][i]=1;int res=1;for(int i=1;i<N;i++){for(int j=0;j<N;j++){dp[i][j]=1;int t1=i,t2=j;while(t1>=0&&t2<N){t1-=dp[i][j];t2+=dp[i][j];if(t1<0||t2>=N) break;if(dp[i][j]==dp[t1][t2]){dp[i][j]*=2;continue;}t1-=1;t2+=1;if(t1<0||t2>=N) break;if(dp[i][j]==dp[t1][t2])dp[i][j]=2*dp[i][j]+1;}res=max(res,dp[i][j]);}}printf("%d\n",res);}return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/IKnowYou0/p/6639349.html

總結(jié)

以上是生活随笔為你收集整理的HDU 2859 Phalanx的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。