AcWing 1222. 密码脱落
原题链接
中等
作者:
深海温水
,
2024-04-06 16:24:09
,
所有人可见
,
阅读 9
答案需要对区间递归求解,一般可以考虑区间DP
区间$[l\sim r]$要回文,至少需要脱落多少个种子
$f[l][r] = min(f[l + 1][r] + 1, f[l][r - 1] + 1)$
如果 $s[l + 1] == s[r - 1],f[l][r] = min(f[l][r], f[l + 1][r - 1])$
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int f[N][N], n;
char s[N];
int main()
{
cin >> s + 1;
n = strlen(s + 1);
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 l = 1; l + len - 1 <= n; l ++)
{
int r = l + len - 1;
f[l][r] = min(f[l + 1][r] + 1, f[l][r - 1] + 1);
if(s[l] == s[r])
{
if(len == 2) f[l][r] = 0;
else f[l][r] = min(f[l][r], f[l + 1][r - 1]);
}
}
cout << f[1][n] << endl;
return 0;
}