HDU 2859 DP (求最大对称子矩阵)
程序员文章站
2022-11-02 11:08:54
题意给一个 N∗NN * NN∗N 的字符串矩阵,求出最大对称子矩阵,对称轴从左下角-->右上角思路:参考代码:#include #include #include #include #include
题意
给一个 的字符串矩阵,求出最大对称子矩阵,对称轴从左下角-->
右上角
思路:
参考代码:
#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
上一篇: Android8.0之后启动服务崩溃