問題描述

蒜頭君喜歡中心對稱的字符串，即回文字符串。現在蒜頭君手里有一個字符串 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

總結

以上是生活随笔為你收集整理的【计蒜客习题】消除字符串的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。