文档章节

小L的项链切割 (回文串)

o
 osc_y8yehimr
发布于 2019/03/20 17:06
字数 470
阅读 16
收藏 0

精选30+云产品,助力企业轻松上云!>>>

题目描述
小T送给了小L了一串项链。为了方便,我们把项链上形态不同钻石用不同的字母表示。这样小L的项链就变成了一个字符串。
小L忽然想把这串项链优美地切割一下,她想把它切割成尽量少的
回文项链,啊也就是回文串。求最少的切割次数。 输入 第一行一个整数T 表示数据组数 下面T组数据,每一组数据: 只有一行,一个只有小写英文字母的字符串,字符串长度 <= 1000。 输出 对于每一组数据,输出将这个字符串能切割成最少的回文串所需切割的次数。 样例输入 Copy 2 abaacca abcd 样例输出 Copy 1 3

感觉没思路的题目应该就是动态规划

 

#include<iostream>
#include<vector>
using namespace std;    
 bool IsPalindRome(string str){//回文判断 
        int end=str.length()-1;
        int start=0;
        while(start<end){
            if(str[start]==str[end]){
                start++;
                end--;
            }else{
                return false;
            }
        }
        return true;
    }
    int minCut(string s) {
        int len=s.length();
        vector<int> dp(len,0);//初始化为0 
        for(int i=0;i<len;i++){
            dp[i]=IsPalindRome(s.substr(0,i+1)) ? 0 : i;//初始化 
            if(dp[i]==0)
                continue;
            else{
                for(int j=1;j<=i;j++){
                    if(IsPalindRome(s.substr(j,i-j+1)))
                        dp[i]=min(dp[i],dp[j-1]+1);
                    else{
                        dp[i]=min(dp[i],dp[j-1]+i-j+1);
                    }
                }
            }
        }
        return dp[len-1];
    }

int main(){
    string str;
    int n;
    cin>>n; 
    while(n--){
        cin>>str;
        cout<<minCut(str)<<endl;
    }
}
View Code

 难点是下面的OK:

int minCut(string s) {
        int len=s.length();
        vector<int> dp(len,0);//初始化为0 
        for(int i=0;i<len;i++){
            dp[i]=IsPalindRome(s.substr(0,i+1)) ? 0 : i;//判断每一步 
            if(dp[i]==0)
                continue;
            else{
                for(int j=1;j<=i;j++){
                    if(IsPalindRome(s.substr(j,i-j+1))) //1--i判断回文串 
                        dp[i]=min(dp[i],dp[j-1]+1);//可以理解 
                    else{
                        dp[i]=min(dp[i],dp[j-1]+i-j+1);//可以理解有点难度 
                    }
                }
            }
        }
        return dp[len-1];
    }

 

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。

暂无文章

Pycharm文件打开方式

Pycharm修改文件默认打开方式 新下载了一个Pycharm,建了个小demo,期间产生了一个sqlite3文件,由于是第一次打开,就弹出选择打开方式的对话框,手一块直接点了个Text,然后就乱码了: 那我...

osc_fi9eaftu
7分钟前
0
0
微信域名检测中反应速度的重要性

随着微信域名检测的普及,越来越多的人重视这方面有个客户是这样跟我说的,他现在用的那个检测有频率限制 最快只能一秒检测一个, 并发多的时候是不能边跳转边检测的, 只能写到计划任务里面...

mkapi01
8分钟前
0
0
状压dp大总结1 [洛谷]

前言 状态压缩是一种\(dp\)里的暴力,但是非常优秀,状态的转移,方程的转移和定义都是状压\(dp\)的难点,本人在次总结状压dp的几个题型和例题,便于自己以后理解分析状态和定义方式 状态压缩...

osc_s28jz759
9分钟前
0
0
aspnet core 2.1中使用jwt从原理到精通一

目录 原理; 根据原理使用C#语言,生成jwt; 自定义验证jwt; 使用aspnetcore 中自带的类生成jwt; 学有所得 了解jwt原理; 使用C#轻松实现jwt生成和验证 原理 jwt对所有语言都是通用的,只要...

osc_1ls4yaq1
10分钟前
0
0
github上DQN代码的环境搭建,及运行(Human-Level Control through Deep Reinforcement Learning)conda配置

最近师弟在做DQN的实验,由于是强化学习方面的东西,正好和我现在的研究方向一样于是我便帮忙跑了跑实验,于是就有了今天的这个内容。 首先在github上进行搜寻,如下图: 发现第一个星数最多...

osc_252iaxru
11分钟前
8
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部