2918:dp怪鸽

时间限制:2 S   /  内存限制:65536 KB
AC:125   /  Submit:338
问题描述

众所周知ovo非常喜欢"dp"这个组合,某一天他得到了一个字符串s,他可以每次花费一点理智把'd'变成'p'或者把'p'变成'd',从而使得这个字符串变成前半段都是'd',后半段都是'p'的字符串

"ddddppp","dpppp","dp" 是合法的

"dpd","ddd","pppddd" 是不合法的

但是ovo希望自己足够理智,所以想要知道能够使得字符串合法的最小理智花费。

输入描述

T组样例

每组样例一行字符串s

输出描述
针对每组样例输出最小理智花费
样例输入复制样例

3

ddddp

pdpdp

ppppp

样例输出

0

2

1

提示说明

针对40%的样例,length(s) <= 100

针对60%的样例,length(s) <= 1000

针对100%的样例,length(s) <= 100000

针对100%的样例,2 <= length(s) 且 所有样例的字符串长度总和不超过 1e6

相关

TKK-ICPC Round#9

题单#5(前缀和、差分数组)


Copyright 2016 - 2024 XUJC ACM Team
闽ICP备2020022076号-1