动态规划与字符串遍历

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
ll n, a[30], m;
ll dp[1000005];
ll ans;
string s;
ll x;
//cal函数提前计算对应连续的abc时获得的最大价值
//例如dp[5] 代表的是连续出现5个abc时能获得的最大价值
void cal() // i是多少个连续的abc    j是获得积分的数量方式（例如 一个abc 两个abc 三个abc ....）
{
    dp[0] = 0,dp[1] = a[1];//初始化
    for (int i = 2;i <= 100000/3;i++)//可以优化成题目输入的数据，这里是直接用数据最大可能性
    {
        for (int j = 1;j <= 20;j++)//可以优化成题目输入的数据，这里是直接用数据最大可能性
        {
            if (i - j >= 0)//下标不为负
                dp[i] = max(dp[i], dp[i - j] + a[j]);
        }
    }
}
int main()
{
    cin >> n;
    for (ll i = 1;i <= n;i++)
        cin >> a[i];
    cin >> m >> s;
    cal();
    for (int i = 0;i < s.size() - 2;i++)//遍历
    {
        string op = "";
        op += s[i], op += s[i + 1], op += s[i + 2];
        //op为连续三个字符
        if (op == "abc")//等于abc就需要看看是连续几个abc
        {
            ll sum = 1;//刚开始默认是1个abc
            int j = i + 3;//刚刚的abc是i,i+1,i+2的位置，所以现在要从i+3开始遍历
            string op1 = "";
            op1 += s[j], op1 += s[j + 1], op1 += s[j + 2];
            //op1拼接三个字符
            while (op1 == "abc"&&j+2<s.size())//等于abc且不越界
            {
                sum++;//计数器+1
                j += 3;//跟上面效果一致
                op1 = "";//清零，不然会影响下一次拼接
                op1 += s[j], op1 += s[j + 1], op1 += s[j + 2];//拼一下新的3个字符
            }
            ans += dp[sum];//当前是sum个连续的abc, dp[sum]就是最大价值
            i = j-1;//最后更新i为j-1(正常应该更新为i = j ，但是要注意for循环有个i++，所以是j-1)
        }
    }
    cout << ans;
    return 0;
}