题目如下：

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

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

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

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

你的任务是：

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

输入格式

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

输出格式

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

数据范围

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

输入样例1：

ABCBA

输出样例1：

0

输入样例2：

ABDCDCBABC

输出样例2：

3

题解 or 思路：

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

状态定义：

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

状态转移：

• 取 $l$ & $r$
  如果 $str[l]=str[r]$
  $dp[l][r]=dp[l+1][r-1]+2$
• 不取 $l$
  $dp[l][r]=max(dp[l][r],dp[l+1][r])$
• 不取 $r$
  $dp[l][r]=max(dp[l][r],dp[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();
}

最后

以上就是幸福小丸子为你收集整理的密码脱落(区间DP)[第七届蓝桥杯省赛C++A/C组,第七届蓝桥杯省赛JAVAC组]题目如下：题解 or 思路：AC 代码如下：的全部内容，希望文章能够帮你解决密码脱落(区间DP)[第七届蓝桥杯省赛C++A/C组,第七届蓝桥杯省赛JAVAC组]题目如下：题解 or 思路：AC 代码如下：所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。