动态规划练习

淩亂°似流年 2022-05-10 14:10 180阅读 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 条评论，180人围观）

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

相关阅读

相关动态规划练习（4）杨辉三角-LeetCode

问题描述：给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。在「杨辉三角」中，每个数是它左上方和右上方的数的和。 ![8a3b52b4d

水深无声/ 2023年09月28日 22:47/ 0 赞/ 6 阅读

相关动态规划练习（1）印章

四大步骤：一：确定状态最后一步化成子问题二：状态转移写出表达式三：初始条件和边界情况四：计算顺序

矫情吗；*/ 2023年09月28日 19:59/ 0 赞/ 19 阅读

相关动态规划练习（2）拿金币

问题描述　　有一个N x N的方格,每一个格子都有一些金币,只要站在格子里就能拿到里面的金币。你站在最左上角的格子里,每次可以从一个格子走到它右边或下边的格子里。请问如

￡神魔★判官ぃ/ 2023年09月28日 15:28/ 0 赞/ 8 阅读

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

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

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

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

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

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

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

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

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

相关动态规划

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

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

相关动态规划练习

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

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

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

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

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

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

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

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