当前位置:   article > 正文

【计蒜客习题】消除字符串

蒜头君是一位信息学家,他在海量的文本数据中寻找包含了 3 3 个关键字的字符串。这

问题描述


蒜头君喜欢中心对称的字符串,即回文字符串。现在蒜头君手里有一个字符串 SS,蒜头君每次都会进行这样的操作:从 SS 中挑选一个回文的子序列,将其从字符串 SS 中去除,剩下的字符重组成新的字符串 SS。 蒜头君想知道,最少可以进行多少次操作,可以消除整个字符串。

 

输入格式


输入一行。输入一个字符串 S(1≤length(S)≤16),字符串均由小写字母组成。


输出格式


输出一行,输出一个整数,表示消除整个字符串需要的最少操作次数。

 

样例输入


abaccba


样例输出


2


 

呃呃,状压DP的经典模型,其实状压DP就是用来解决这类集合相关问题的。

每次都是删去集合的子集,我们可以通过枚举子集来解决。如果一个集合是回文序列,dp为1;否则就是其子集的dp值之和的最小值。

这道题唯一需要好好写的是判断回文序列。。。(dalao请忽略)

 1 #include<cstdio>
 2 #include<cstring>
 3 inline int min(int a,int b) {return a<b?a:b;}
 4 const int maxn=20,inf=0x3f3f3f3f;
 5 int dp[1<<maxn],len;
 6 bool ok[1<<maxn];
 7 char s[maxn];
 8 inline bool judge(int i) {
 9     int h=len,l=0;
10     while(h>l) {
11         while(!((1<<h)&i)) --h;
12         while(!((1<<l)&i)) ++l;
13         if(s[h]!=s[l]) return false;
14         --h,++l;
15     }
16     return true;
17 }
18 int main() {
19     scanf("%s",s);
20     len=strlen(s);
21     memset(dp,inf,sizeof(dp));
22     dp[0]=0;
23     for(int i=1;i<(1<<len);++i) {
24         if(judge(i)) {dp[i]=1;continue;}
25         for(int j=i;j;j=(j-1)&i) {
26             if(j==i) continue;
27             dp[i]=min(dp[i],dp[i-j]+dp[j]);
28         }
29     }
30     printf("%d",dp[(1<<len)-1]);
31     return 0;
32 }
AC代码

 

转载于:https://www.cnblogs.com/Mr94Kevin/p/9636979.html

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/木道寻08/article/detail/799602
推荐阅读
相关标签
  

闽ICP备14008679号