动态规划练习

淩亂°似流年 2022-05-10 14:10 160阅读 0赞

这一天zdw说了一个很长的字符串，只包括 ‘y’ , ‘i’ , ‘n’ ,’g’这四个字符。你需要选取尽量多的下标，让这些下标在这个字符串中对应的字符按下标从小到大的顺序组起来是一个”yyyyiiinngggg”这样的字符串。其中’y’,’i’,’n’,’g’这些字符的个数为0也算是合法的。比如”yngg”和”g”都是合法的答案

现在cy想知道，最多能选多少下标，令其合法？

输入数据：

第一行一个T，表示有T组数据

T行每行一个字符串，只包含’y’, ’i’ , ’n’ , ’g’这四个小写字母

输出：

T行每行一个整数，代表最多能选取多少下标。

数据范围

T<=10

对于30%的数据：|s|<=10;

对于另10%的数据：只包含一种字母,|s|<=100000;

对于100%的数据：|s|<=100000

样例1：

INPUT

1

ygniyging

OUTPUT

5

样例2：

INPUT

2

y

ing

OUTPUT

1

3

## 输入 ##

## 输出 ##

## 提示 ##

## 来源 ##

[cy1999][]

#include<iostream>
    using namespace std;
    int main(){
        int T;
        cin>>T;
        char s[100020];
        int y,yi,yin,ying;
        while(T--){
            y=0;yi=0;yin=0;ying=0;
            cin>>s;
            int i=0;
            while(s[i]!='\0'){
                switch(s[i]){
                    case 'y':y++;break;
                    case 'i':yi++;break;
                    case 'n':yin++;break;
                    case 'g':ying++;break;
                }
                if(y>yi)yi=y;
                if(yi>yin)yin=yi;
                if(yin>ying)ying=yin;
                i++;
            }
            cout<<ying<<endl;
        }
    }

[cy1999]: https://www.ckoj.top/problemset.php?search=cy1999

发表评论取消回复

表情：

评论列表（有 0 条评论，160人围观）

还没有评论，来说两句吧...

相关阅读

相关 Open Judge——动态规划练习

目录了解动态规划 2760:数字三角形 1、题目 2、代码 4120:硬币 1、题目 2、代码 -------------------- 了解动态规划

刺骨的言语ヽ痛彻心扉/ 2023年09月27日 22:44/ 0 赞/ 103 阅读

相关算法刻意练习之动态规划

1 特点 1.1 动态规划和递归或者分治没有根本上的区别（关键看有无最优的子结构) 1.共性:找到重复子问题； 2.差异性:最优子结构、中途可以淘太欠优解；

我不是女神ヾ/ 2022年12月21日 06:25/ 0 赞/ 190 阅读

相关动态规划（练习题目，）

[http://www.cnblogs.com/lzmfywz/archive/2012/02/15/2353320.html][http_www.cnblogs.com_lz

男娘i/ 2022年09月18日 00:52/ 0 赞/ 227 阅读

相关动态规划

首先是概念:动态规划就是将原问题划分为简单的几个小问题（有点类似与分治法?但是分治法中的各个小问题是相互独立的，彼此之间不会产生影响，但是动态规划中所得的值和前面相关，当前的解

青旅半醒/ 2022年07月12日 05:01/ 0 赞/ 297 阅读

相关动态规划

等我有时间了，一定要把《算法导论》啃完，这本书的印刷质量实在太好了，就是烧脑子，滑稽。适合应用动态规划求解的最优化问题应该具备两个要素：最优子结构：一个问题的最优解包含

短命女/ 2022年05月17日 09:45/ 0 赞/ 294 阅读

相关动态规划

1.题目：最长递增子序列（Longest Increasing Subsequence）问题描述： > 给定长度为N的数组A，计算A的最长单调递增的子序列（不一定连续）

妖狐艹你老母/ 2022年05月11日 04:56/ 0 赞/ 260 阅读

相关动态规划练习

这一天zdw说了一个很长的字符串，只包括 ‘y’ , ‘i’ , ‘n’ ,’g’这四个字符。你需要选取尽量多的下标，让这些下标在这个字符串中对应的字符按下标从小到大的顺序组起

淩亂°似流年/ 2022年05月10日 14:10/ 0 赞/ 161 阅读

相关动态规划-------入门练习2

题目一：假设有n个数从n个数中找出任意个不相邻的数求和计算出这个和的最大值输入： 5 4 1 1 9 1 输出： 13 （最好的方案为4+

比眉伴天荒/ 2022年04月17日 04:51/ 0 赞/ 212 阅读

相关动态规划 -----入门练习1

现在1~Q个时间段内有n（n<100）个工作，每个工作都有各自的开始时间start，结束时间end和工作所得钱p,工作时间有重叠，现问在这段时间内所得钱最多为多少？

末蓝、/ 2022年04月17日 03:49/ 0 赞/ 230 阅读

相关动态规划

算法题中动态规划是真的难，写一篇总结，彻底解决动态规划。参考：[https://blog.csdn.net/u013309870/article/details/7519359

左手的ㄟ右手/ 2021年11月19日 14:14/ 0 赞/ 465 阅读