HDU 4628(动态规划-状压dp)

女爷i 2022-06-01 04:59 193阅读 0赞

问题描述:

You heart broke into pieces.My string broke into pieces.But you will recover one day,and my string will never go back.   
Given a string s.We can erase a subsequence of it if this subsequence is palindrome in one step. We should take as few steps as possible to erase the whole sequence.How many steps do we need?   
For example, we can erase abcba from axbyczbea and get xyze in one step.

Input

The first line contains integer T,denote the number of the test cases. Then T lines follows,each line contains the string s (1<= length of s <= 16).   
T<=10.

Output

For each test cases,print the answer in a line.

Sample Input

2
    aa
    abb

Sample Output

1
    2

题目题意:问最小次数可以删除整个串，每次删除只能是非连续的回文子串。

题目分析:首先我们先得求取所有的回文字串可能，然后就状压dp就好了 dp\[i\]表示到状态i的最小次数

代码如下:

#include<iostream>
    #include<cstdio>
    #include<cmath>
    #include<string>
    #include<cstring>
    #include<vector>
    using namespace std;
    
    const int inf=1e9+7;
    string str;
    vector<int> vec;
    int dp[1<<16];
    bool check(int n)
    {
        vector<char > s;
        for (int i=0;i<16&&((1<<i)<=n);i++) {
            if (n&(1<<(i))) s.push_back(str[i]);
        }
        int left=0,right=s.size()-1;
        while (right>=left) {
            if (s[right]!=s[left]) return false;
            right--;
            left++;
        }
        return true;
    }
    void init(int n)
    {
        vec.clear();
        for (int i=1;i<(1<<n);i++) {
            if (check(i)) vec.push_back(i);
        }
    }
    int main()
    {
        int t;
        scanf("%d",&t);
        while (t--) {
            cin>>str;
            init(str.size());
            int len=str.size();
            for (int i=0;i<=((1<<len)-1);i++) {
                dp[i]=inf;
            }
            dp[0]=0;
            for (int i=0;i<=((1<<len)-1);i++) {
                if (dp[i]==inf) continue;
                for (int j=0;j<vec.size();j++) {
                    if (!(i&(vec[j]))) {
                        dp[i|vec[j]]=min(dp[i|vec[j]],dp[i]+1);
                    }
                }
            }
            printf("%d\n",dp[(1<<len)-1]);
        }
        return 0;
    }