时尚网站建设,网站建设公司投融资分析,网站设计与建设,psd素材免费下载网址Phalanx HDU - 2859 这是一道非常好的题目#xff0c;我实在是没想到该怎么做#xff0c;看了一下大神的题解才恍然大悟#xff08;还有这种操作#xff1f;#xff09;
由于对称矩阵是以对称轴进行对称的#xff08;废话#xff09;#xff0c;所以我们可以用dp[i][j… Phalanx HDU - 2859 这是一道非常好的题目我实在是没想到该怎么做看了一下大神的题解才恍然大悟还有这种操作
由于对称矩阵是以对称轴进行对称的废话所以我们可以用dp[i][j]表示(i,j)所经过的主轴线并且以(i,j)为左下角的最大的对称矩阵。
这样的话我们再考虑左下方的一个元素(i1,j-1),如果从这个点出发向上有k个元素与从这个点出发向右的k个元素对应相等。
我们接着考虑k的大小如果k刚好等于dp[i][j]那么这个对称矩阵可以继续扩大
这样的话我们可以得到递推方程dp[i1][j-1] dp[i][j] 1
如果k dp[i][j]的话那么
dp[i-1][j1] min(k1,dp[i][j 1]);
AC代码 #include iostream
#include algorithm
#include cstring
#include cstdio
using namespace std;
int n;
const int MAX 1003;
int mtx[MAX][MAX];
int dp[MAX][MAX];
int main(){while(scanf(%d,n) n){memset(dp,0,sizeof(dp));for(int i 1;i n;i){for(int j 1;j n;j){scanf( %c,mtx[i][j]);}}int ans 1;for(int i 1;i n;i){for(int j 1;j n;j){dp[i][j] 1;int cnt 0;for(int t 1;t min(i,n-j1);t){if(mtx[i-t][j] ! mtx[i][jt])break;cnt;if(cnt dp[i-1][j1])break;}dp[i][j] min(dp[i-1][j1] 1,cnt1);ans max(ans,dp[i][j]);}}coutansendl;}return 0;
}
