牛客----String of CCPC

牛客----String of CCPC

​​题目描述​​

宝宝刚刚在他的口袋里发现了一个长度为n的字符串s，由’C’和’P’组成。作为中国大学生程序设计大赛的忠实粉丝，包宝认为 s 的子串 sisi+1si+2si+3 是“好”的，当且仅当 si=si+1=si+3= ‘C’ ，并且 si+ 2=‘P’，其中 si 表示字符串 s 中的第 i 个字符。 s 的值是 s 中不同“好”子串的数量。两个“好”子串 sisi+1si+2si+3 和 sjsj+1sj+2sj+3 是不同的，当且仅 i ≠ j 。

为了让这个字符串更有价值，宝宝决定从字符商店购买一些字符。每次他可以从商店购买一个’C’或一个’P’，并将角色插入s中的任何位置。但一切都是有代价的。如果是宝宝第 i 次购买角色，他将需要花费 i - 1 个单位的价值。

BaoBao 得到的最终值是 s 的最终值减去从商店购买的所有角色的总成本。请帮助宝宝最大化最终价值。

输入描述：

有多个测试用例。输入的第一行包含一个整数 T，表示测试用例的数量。对于每个测试用例：

第一行包含一个整数 n (1 ≤ n ≤ 2 ×105)，表示字符串的长度。

第二行包含由 ‘C’ 和 ‘P’ 组成的字符串 s (|s| = n)。

保证所有测试用例的 n 之和不超过 106。

输出描述：

对于每个测试用例输出一行，包含一个整数，表示宝宝可以得到的最大最终值。

示例1输入

33CCC5CCCCP4

示例1输出

111

思路分析: 题目的要求是,通过插入C和P,然后得到最多可以形成CCPC序列的数量,但是购买字符的价格是购买次数(i)的i-1. 所以第一次购买是免费的,第二次购买即使能够拼成序列,但得到的总的受益是和不买一样的.之后,购买两次之上就很不划算了.所以如果要购买,就购买一次. 算法步骤:

1.先统计可以形成CCPC的.2.判断是不是CCC,CCP,CPC开头的,如果是可以购买,并且要购买只能购买一次,超过一次.价格就越来越贵,不划算了.3.对于CCC情况,要防止这种CCCPC,为了形成一个而拆开一个是不划算的.

AC代码:

//namespace std;int t,n,flag,ans;char arr[1000000+5]; //1.先统计可以形成CCPC的. //2.判断是不是CCC,CCP,CPC开头的,如果是可以购买,并且要购买只能购买一次,超过一次.价格就越来越贵,不划算了. //3.对于CCC情况,要防止这种CCCPC,为了形成一个而拆开一个是不划算的. CCPCCCPCint main(){ cin>>t; while(t--){ cin>>n; getchar(); flag = 0; ans = 0; for(int i = 0; i < n; i++){ cin>>arr[i]; } arr[n]=arr[n+1]='*'; //进行遍历 for(int i = 0; i < n-2;i++){ //cout<

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。