对称矩阵dp -- Phalanx HDU - 2859

Phalanx HDU - 2859

题意：
给你一个n * n 的矩阵。矩阵由大小写字母组成，找关于左下角到右上角对角线对称的子矩阵，求能找到的最大的子矩阵大小。

思路：
观察矩形对称的特点，dp[i][j]存以（i, j）为右下角的最大对称矩形大小，从左上到右下递推，转移式为 dp[i][j] = k，显然k不会超过 dp[i - 1][j + 1] + 1，

code：

#include
#include
#include
#include
#include
#include
using namespace std;
const int maxn = 1e3 + 5;
char s[maxn][maxn];
int dp[maxn][maxn];void init(){memset(dp, 0, sizeof(dp));
}int main(){int n;while(scanf("%d", &n), n != 0){for(int i = 0; i < n; i++)scanf("%s", s[i]);init();int ans = 1;for(int i = 0; i < n; i++)for(int j = n - 1; j >= 0; j--){dp[i][j] = 1;if(i == 0 || j == n - 1) continue;   //处理边界int x = dp[i - 1][j + 1];for(int k = 1; k <= x; k++)if(s[i - k][j] == s[i][j + k]) dp[i][j]++;	//找到以（i, j）为左下角的最大矩阵	   	      	 else break;	ans = max(ans, dp[i][j]);				  }  printf("%d\n", ans);}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！