HDU 2859 Phalanx

简单二维dp。o(n^3)效率过的。不知道有没有o(n^2)的解法。

为了方便点,先左右交换一下。

dp[i][j]表示以[i,j]为左上角的最大对称矩阵长度

那么dp[i][j]=min(Max,dp[i+1][j+1])+1;

其中Max是以[i,j]为起点,i这一行和j这一列最长公共前缀的长度

#include<cstdio>
#include<cstring>
#include<cmath>
#include<stack>
#include<vector>
#include<string>
#include<iostream>
#include<algorithm>
using namespace std; const int maxn=+;
char Map[maxn][maxn];
int dp[maxn][maxn];
int n; int main()
{
while(~scanf("%d",&n))
{
if(!n) break;
for(int i=; i<n; i++) scanf("%s",Map[i]);
for(int i=; i<n; i++)
for(int j=; j<n/; j++)
swap(Map[i][j],Map[i][n-j-]); memset(dp,,sizeof dp); int ans=;
for(int i=n-; i>=; i--)
{
for(int j=n-; j>=; j--)
{
int Max=;
for(int len=;; len++)
{
if(i+len>=n||j+len>=n||Map[i][len+j]!=Map[len+i][j])
{
Max=len;
break;
}
}
Max--;
dp[i][j]=min(Max,dp[i+][j+])+;
ans=max(ans,dp[i][j]);
}
}
printf("%d\n",ans);
}
return ;
}
上一篇:DEV提示控件ToolTipControl


下一篇:LeetCode(61)-Valid Palindrome