給出一行字符串,每次可以刪去一個回文子串,子串可以是不連續的,因此用狀壓比較好模擬,求刪掉整個字符串需要的最少步數。
字符串的最大長度為16,因此不能逐行枚舉狀態,首先預處理出來所有的的回文子串,然後從第一步開始,依次狀壓第i步能到達的狀態,如果能達到母串,跳出。
還有初始化不要用圖省事用memset。。不優越的姿勢+函數導致T了數發。
#include#include #include #include #include #include #include #include using namespace std; char s[20]; char s1[20]; int ans; int num; int dp[1<<17][17]; int visit[20]; int Pow[15]; int a[1<<17]; bool solve(char str[]) { int flag=1; int start=0; int end=strlen(str)-1; while(start<=end) { if(str[start]!=str[end]) { flag=0; break; } start++; end--; } if(flag) { return true; } else { return false; } } int main() { int t; int sum; Pow[0]=1; for(int i=1;i<=18;i++) { Pow[i]=Pow[i-1]*2; } scanf("%d",&t); while(t--) { num=0; scanf("%s",s); int len=strlen(s); int mos=1<<(len); for(int i=1;i<=len;i++) { for(int j=1;j