Pieces 题解(状压dp+$3^n$枚举子集)

本文主要是介绍Pieces 题解(状压dp+$3^n$枚举子集)，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目链接

题目大意

有一个长度不超过 16 的字符串。每次你可以从中删除一个子序列，但是要求这个子序列是回

文的。问最少删除几次可以把这个字符串删光。

题目思路

这个数据很小 很明显是状压\(dp\)

设\(dp[i]\)表示删除\(i\)的最小操作数 那么答案显然为\(dp[(1<<n)-1]\)

然后直接枚举子集\(dp\)转移即可

所有元素子集的总个数为\(3^n\)

考虑贡献如果\(x\)集合有\(k\)个\(1\) 那么子集有\(x\)的有\(2^{n-k}\)个

则总和为\(\Large\sum_{k=0}^{k=n}C(n,k)2^{n-k}=(1+2)^n=3^n\)

枚举 x 的子集代码：
for(int i = x; i; i = (i - 1) & x){
// i 就是 x 的子集
}

代码

#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<vector>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#define se second
#define debug cout<<"I AM HERE"<<endl;
using namespace std;
typedef long long ll;
const int maxn=1e5+5,inf=0x3f3f3f3f,mod=1e9+7;
const double eps=1e-6;
char s[maxn],temp[maxn];
bool flag[1<<16];
int dp[1<<16],n;
bool check(int x){
    int len=0;
    // [0,len-1]
    for(int i=0;i<n;i++){
        if(x&(1<<i)){
            temp[len++]=s[i];
        }
    }
    for(int i=0;i<=len-1;i++){
        if(temp[i]!=temp[len-1-i]) return 0;
    }
    return 1;
}
signed main(){
    int _;scanf("%d",&_);
    while(_--){
        scanf("%s",s);
        n=strlen(s);
        memset(dp,0x3f,sizeof(dp));
        for(int i=0;i<=(1<<n)-1;i++){
            flag[i]=check(i);
        }
        dp[0]=0;
        for(int i=1;i<=(1<<n)-1;i++){
            for(int j=i;;j=(j-1)&i){
                if(dp[j]==inf) continue;
                if(flag[i^j]){
                    dp[i]=min(dp[i],dp[j]+1);
                }
                if(!j) break;
            }
        }
        printf("%d\n",dp[(1<<n)-1]);
    }
    return 0;
}

这篇关于Pieces 题解(状压dp+$3^n$枚举子集)的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！