欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  移动技术

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

程序员文章站 2022-11-02 11:08:54
题意给一个 N∗NN * NN∗N 的字符串矩阵,求出最大对称子矩阵,对称轴从左下角-->右上角思路:参考代码:#include #include #include #include #include #include #include #include ...

题意
给一个 NNN * N 的字符串矩阵,求出最大对称子矩阵,对称轴从左下角-->右上角
思路:
HDU 2859 DP (求最大对称子矩阵)
HDU 2859 DP (求最大对称子矩阵)
参考代码:

#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