AcWing 1222. 密码脱落
原题链接
中等
作者:
ヅ忆柳
,
2022-12-01 13:47:18
,
所有人可见
,
阅读 237
由题意判断属于区间DP
该题属于区间DP中的判断是否回文,在DP中判断是否回文就是dp[l][r] 与 dp[l + 1][r - 1] 之间的再判断
l 为子串左节点, r 为子串右节点
例如当s[l] == s[r] 时dp[l][r] = dp[l + 1][r - 1] + 2 -- s[l] == s[r] 意味着我可以为(l + 1, r - 1)中的回文序列加上2。
dp[l][r] = dp[l + 1][r - 1] + 2;
当s[l] != s[r] 时不能让状态断掉, 可以去取在区间(l, r)中的最长回文串
dp[l][r] = max(dp[l + 1][r], dp[l][r - 1]);
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int dp[N][N];
int main()
{
string s;
cin >> s;
int n = s.size();
s = ' ' + s;
int ans = 1;//再怎么样答案至少为1
for (int len = 1; len <= n; len ++)
{
for (int l = 1; l + len - 1 <= n; l ++)
{
int r = l + len - 1;
if (len <= 1) {dp[l][r] = 1;continue;}//长度为1直接为回文串跳过
else if (s[l] == s[r])
{
dp[l][r] = dp[l + 1][r - 1] + 2;
}
else
{
dp[l][r] = max(dp[l][r - 1], dp[l + 1][r]);
}
ans = max(dp[l][r], ans);
//cout << dp[l][r] << " " << l << " " << r << '\n';
}
}
cout << n - ans << '\n';
//cout << n << '\n';
return 0;
}
tql
太强了