编程介的小学生 2017-11-17 11:03 采纳率: 20.5%
浏览 457
已结题

Pieces

Problem Description
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

  • 写回答

1条回答 默认 最新

  • HHi3s 2018-08-03 21:52
    关注
    /**
            就算是简单题,我都感觉做不出来……不会表示状态,那就什么都做不出来……
    **/
    #include<iostream>
    #include<vector>
    #include<cstdio>
    #include<cstring>
    
    using namespace std;
    #define maxn 16
    
    char s[25];
    int len =0;
    int all=0;  //all state
    int dp[1<<maxn+1];
    
    int init(int x)   /**判断某个状态对应的字符串的回文串的大小,如果字符串全部回文,返回1,否则返回字符串的长度**/
    {
        int st[maxn+1]= {0},f=0; //stack    first *p
                                 /**用栈来储存x状态时,每一个存在的字符所对应的位置**/
        for(int i=0; i<=len; i++)
            if(x&(1<<i))
                st[f++]=i;
        f--;
        for(int j=0; j<f/2; j++)   /**从中点向两边看,是否回文,如果发现不回文的任意两个个字母,就返回状态x的字符串长度**/
            if(s[st[j]]!=s[st[f-j]])
                return f+1;
        return 1;
    }
    /**表示状态,实际上就是用01串来表示原来字符串每个字符是否被删掉,0对应的是被删掉的,1表示留下的**/
    void DP()
    {
        len=strlen(s);
        all=1<<len;      
        /**初始的状态是11111……111,就是全部都存在**/
        all--;
        //cout<<all<<endl;
        for(int i=1; i<=all; i++) /**枚举各种状态,对其进行初始化**/
        {
            dp[i]=init(i);        /**对每一个dp状态初始化**/
            //cout<<i<<"  "<<dp[i]<<endl;
            for(int s0=i; s0>0; s0=(s0-1)&i)    /**枚举每一个状态的子状态,
                                             dp[状态i]=min(dp[状态i],dp[子状态s0]+dp[子状态相对与状态i的补集s0^i]),二进制和位运算的灵活运用**/
                dp[i]=min(dp[i],dp[s0]+dp[s0^i]);
        }
    }
    
    void print()
    {
        printf("%d\n",dp[all]);
    }
    
    void read()
    {
        int n;
        cin>>n;
        while(n--)
        {
            memset(dp,0,sizeof(dp));
            cin>>s;
            DP();
            print();
        }
    }
    
    int main()
    {
        read();
        return 0;
    }
    
    
    评论

报告相同问题?

悬赏问题

  • ¥15 MATLAB怎么通过柱坐标变换画开口是圆形的旋转抛物面?
  • ¥15 寻一个支付宝扫码远程授权登录的软件助手app
  • ¥15 解riccati方程组
  • ¥15 display:none;样式在嵌套结构中的已设置了display样式的元素上不起作用?
  • ¥15 使用rabbitMQ 消息队列作为url源进行多线程爬取时,总有几个url没有处理的问题。
  • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决
  • ¥50 树莓派安卓APK系统签名
  • ¥65 汇编语言除法溢出问题
  • ¥15 Visual Studio问题
  • ¥20 求一个html代码,有偿