题目链接: mari和shiny
动态规划求解, 单纯定义一个状态表示不够, 需要定义三个状态表示, 分别为:
- s[i]: 表示区间 [0, i] 中最多有多少个 's'. 其状态转移方程可分为两种情况: 1) 当遍历到的字符是 's' 时为 s[i] = s[i - 1] + 1, 否则为 s[i] = s[i - 1].
- h[i]: 表示区间 [0, i] 中最多有多少个 "sh". 其状态转移方程可分为两种情况: 1)当遍历到的字符是 'h' 时为 h[i] = s[i - 1] + h[i - 1], 否则为 h[i] = h[i - 1].
- y[i]: 表示区间 [0, i] 中最多有多少个 "shy". 其状态转移方程可分为两种情况: 1)当遍历到的字符是 'y' 时为 y[i] = h[i - 1] + y[i - 1], 否则为 y[i] = y[i - 1].
正常来写要开三个数组存放每次的结果, 但是可以使用三个变量来分别记录结果, 达到空间优化的目的, 题解代码如下:
#include <iostream>
using namespace std;
int main()
{
int n = 0;
cin >> n;
string str;
cin >> str;
long s = 0;
long h = 0;
long y = 0;
for(int i = 0; i < n; ++i)
{
if(str[i] == 's')
{
s++;
}
else if(str[i] == 'h')
{
h += s;
}
else if(str[i] == 'y')
{
y += h;
}
}
cout << y << endl;
return 0;
}