当前位置： 移动技术网 > 移动技术>移动开发>IOS > HDU 2859 DP (求最大对称子矩阵）

HDU 2859 DP (求最大对称子矩阵）

2020年07月14日  | 移动技术网移动技术  | 我要评论

题意
给一个 N∗NN * N 的字符串矩阵，求出最大对称子矩阵，对称轴从左下角-->右上角
思路：
在这里插入图片描述
在这里插入图片描述
参考代码：

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <cstring>
#include <cstdlib>
#include <math.h>
using namespace std;
typedef long long ll;
const int N = 1005;
const int maxn = 1e6 + 5;
ll a[maxn], b[maxn];
double x[N], y[N];
char s[N][N];
int dp[N][N];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	while (cin >> n && n)
	{
		memset(dp, 0, sizeof dp);
		memset(s, 0, sizeof s);
		for (int i = 1; i <= n; i++)
			cin >> (s[i] + 1);
		for (int i = 1; i <= n; i++)
			dp[i][n] = dp[1][i] = 1;
		int m = 1;
		for (int i = 1; i <= n; i++)
		{
			for (int j = 1; j <= n; j++)
			{
				if (i == 1 || j == n)
					continue;
				int x = i, y = j;
				while (x >= 1 && y <= n && s[x][j] == s[i][y])
					x--, y++;
				int ans = i - x;
				if (ans >= dp[i - 1][j + 1] + 1)
					dp[i][j] = dp[i - 1][j + 1] + 1;
				else
					dp[i][j] = ans;
				m = max(m, dp[i][j]);
			}
		}
		cout << m << endl;
	}
}

本文地址：https://blog.csdn.net/yangzijiangac/article/details/107319437

您可能感兴趣的文章:

如对本文有疑问， 点击进行留言回复！！

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网