首页 > ACM题库 > HDU-杭电 > HDU 4628-Pieces-动态规划-[解题报告]HOJ
2015
09-17

HDU 4628-Pieces-动态规划-[解题报告]HOJ

Pieces

问题描述 :

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.

输入:

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.

输出:

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.

样例输入:

2
aa
abb

样例输出:

1
2

点击打开链接

题目大意:

给一个字符串,每次可以删除一个可不连续回文子串,问最少删几次可以全部删完。

思路:

因为字符串长度最大16,所以可用二进制状态表示, 1表示选取这个字符,0不选,组成一个子串。

先预处理出所有状态,看这个状态是不是回文。

f[i]表示状态i最少几次可以全删完, 初始化f数组INF

f[i] = min{f[i], f[s]+1 } s是i的子集。

 #include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
using namespace std;

typedef long long int64;
const int INF = 0x3f3f3f3f;
const int MAXN = (1<<16)+10;

char str[20];
bool check[MAXN];
int f[MAXN];
int maxSta;

bool isPalind(int st, int len){
    char sub[20];
    int idx = 0;
    for(int i=0; i<len; ++i){
        if( (st>>i)&1 )  
            sub[idx++] = str[i];
    }
    for(int i=0; i<idx/2; ++i){
        if(sub[i] != sub[idx-1-i]) 
            return false;
    }
    return true;
}

int main(){

    int T;
    scanf("%d", &T);
    check[0] = false;
    while(T--){
     
        scanf("%s", str);
        int len = strlen(str);
        maxSta = (1<<len)-1;
        for(int i=1; i<=maxSta; ++i){
            check[i] = isPalind(i, len);                       
        }

        memset(f, 0x7f, sizeof(f));
        f[0] = 0;
        for(int i=1; i<=maxSta; ++i){
            for(int s=i; s; s=(s-1)&i)
                if(check[s])
                    f[i] = min(f[i], f[i^s]+1);
        }
        printf("%d\n", f[maxSta]);

    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/shuangde800/article/details/9665735