密码脱落(区间DP)[第七届蓝桥杯省赛C++A/C组,第七届蓝桥杯省赛JAVAC组]

阿里云国内75折回扣微信号：monov8

阿里云国际，腾讯云国际，低至75折。AWS 93折免费开户实名账号代冲值优惠多多微信号：monov8 飞机：@monov6

题目如下

$X$ 星球的考古学家发现了一批古代留下来的密码。

这些密码是由 $A 、 B 、 C 、 D$ 四种植物的种子串成的序列。

仔细分析发现这些密码串当初应该是前后对称的也就是我们说的镜像串。

由于年代久远其中许多种子脱落了因而可能会失去镜像的特征。

你的任务是

给定一个现在看到的密码串计算一下从当初的状态它要至少脱落多少个种子才可能会变成现在的样子。

输入格式

共一行包含一个由大写字母 $A BC D$ 构成的字符串表示现在看到的密码串。

输出格式

输出一个整数表示至少脱落了多少个种子。

数据范围

输入字符串长度不超过 $1000$

输入样例1

ABCBA

输出样例1

输入样例2

ABDCDCBABC

输出样例2

题解 or 思路

经典区间dp问题
将问题转化成 $l e n$ - $l$ 到 $r$ 最长回文串的长度

状态定义

$d p [l] [r]$ 在 $l$ 到 $r$ 区间最长回文串的长度

状态转移

取 $l$ & $r$
如果 $s t r [l] = s t r [r]$
$d p [l] [r] = d p [l + 1] [r - 1] + 2$
不取 $l$
$d p [l] [r] = ma x (d p [l] [r], d p [l + 1] [r])$
不取 $r$
$d p [l] [r] = ma x (d p [l] [r], d p [l] [r - 1])$

AC 代码如下

const int N = 1009;
char s[N];
int dp[N][N];
void solve()
{
    cin >> s + 1;
    int len = strlen(s + 1);
    for (int i = 1; i <= len; i++)
        for (int j = 1; j + i - 1 <= len; j++)
        {
            int l = j, r = j + i - 1;
            if (l == r)
                dp[l][r] = 1;
            else
            {
                if (s[l] == s[r])
                    dp[l][r] = dp[l + 1][r - 1] + 2;
                dp[l][r] = max(dp[l][r], dp[l + 1][r]);
                dp[l][r] = max(dp[l][r], dp[l][r - 1]);
            }
        }
    cout << len - dp[1][len] << '\n';
}
int main()
{
    solve();
}