[蓝桥杯][2016年第七届真题]密码脱落（记忆化搜索）

题目描述
X星球的考古学家发现了一批古代留下来的密码。
这些密码是由A、B、C、D 四种植物的种子串成的序列。
仔细分析发现，这些密码串当初应该是前后对称的（也就是我们说的镜像串）。
由于年代久远，其中许多种子脱落了，因而可能会失去镜像的特征。

你的任务是：
给定一个现在看到的密码串，计算一下从当初的状态，它要至少脱落多少个种子，才可能会变成现在的样子
输入
输入一行，表示现在看到的密码串（长度不大于1000）
输出
要求输出一个正整数，表示至少脱落了多少个种子。
样例输入
ABCBA
样例输出
0
样例输入
ABDCDCBABC
样例输出
3
dotcpp平台真的是缺斤少两，不仅错误数据多而且连样例数据还不给完整了。。第二个样例是应有的。
思路：从两头开始遍历，遇见不一样的字符，这个时候我们就要考虑是从左边取比较好还是右边取比较好了，这就需要比较了。在dfs的时候，会重复遇见很多情况，因此需要记忆化一下。
代码如下：

#include<bits/stdc++.h> #define ll long long using namespace std;const int maxx=1e3+100; int dp[maxx][maxx]; string s; int n;inline int dfs(int l,int r) {if(l==r) return dp[l][r]=0;if(l>r) return 0;if(dp[l][r]!=-1) return dp[l][r];int ans=0;int i=l,j=r;while(s[i]==s[j]&&i<=j) i++,j--;if(i<j) ans=min(dfs(i+1,j),dfs(i,j-1))+1;return dp[l][r]=ans; } int main() {cin>>s;n=s.length();memset(dp,-1,sizeof(dp));int ans=dfs(0,n-1);printf("%d\n",ans);return 0; }

努力加油a啊，(^o)/~

总结

以上是生活随笔为你收集整理的[蓝桥杯][2016年第七届真题]密码脱落（记忆化搜索）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。