AcWing 1222. 密码脱落 正向求解以及反向求解
原题链接
中等
作者:
Snrise
,
2024-04-04 19:39:16
,
所有人可见
,
阅读 1
正向求解
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#define endl '\n'
#define int long long
using namespace std;
const int N = 1010;
char s[N];
int f[N][N];
// f[i][j]表示把区间[i,j]内的字符串变成回文串需要删除的字符的个数;
int n;
signed main(void)
{
std::ios::sync_with_stdio(false);
cin >> (s + 1);
n = strlen(s + 1);
// cout << n << endl;
memset(f, 0x3f, sizeof(f));
for (int i = 1; i <= n; i++)
{
f[i][i] = 0;
}
for (int len = 2; len <= n; len++)
{
for (int i = 1; i + len - 1 <= n; i++)
{
int j = i + len - 1;
f[i][j] = min(f[i + 1][j], f[i][j - 1]) + 1;
if (s[i] == s[j])
{
f[i][j] = min(f[i][j], f[i + 1][j - 1]);
}
}
}
cout << f[1][n] << endl;
return 0;
}
反向求解
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#define endl '\n'
#define int long long
using namespace std;
const int N = 1010;
char s[N];
int f[N][N];
// f[i][j]表示把区间[l,r]内的最长回文子串的长度;
int n;
signed main(void)
{
std::ios::sync_with_stdio(false);
cin >> (s + 1);
n = strlen(s + 1);
// cout << n << endl;
for (int i = 1; i <= n; i++)
{
f[i][i] = 1;
}
for (int len = 2; len <= n; len++)
{
for (int i = 1; i + len - 1 <= n; i++)
{
int j = i + len - 1;
f[i][j] = max(f[i + 1][j], f[i][j - 1]);
if (s[i] == s[j])
{
f[i][j] = max(f[i][j], f[i + 1][j - 1] + 2);
}
}
}
cout << n - f[1][n] << endl;
return 0;
}