题解 | #nico和niconiconi#

典型的线性动态规划。
使用前缀和的思路，建立一个数组用于存储字符串str前i个字符中最大的值，然后寻找其递推关系。
显然，每遍历一个字符，都要判断其前i个字符中最大的前缀和的a, b, c的状态，有可能仅是增加1个a, b, c，亦有可能增加3个a，减少一个c。
最后，前缀和数组中的末项即为整个字符串最大的值。

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main(){
    int n, a, b, c;
    cin >> n >> a >> b >> c;
    string str;
    cin >> str;
    vector<long long> res(n, 0);
    for(int i = 1;i < str.size();i++){
        res.at(i) = res.at(i - 1);
        if(i > 2 && !str.substr(i - 3, 4).compare("nico")){
            res.at(i) = max(res.at(i), res.at(i - 3) + a);
        }
        if(i > 4 && !str.substr(i - 5, 6).compare("niconi")){
            res.at(i) = max(res.at(i), res.at(i - 5) + b);
        }
        if(i > 8 && !str.substr(i - 9, 10).compare("niconiconi")){
            res.at(i) = max(res.at(i), res.at(i - 9) + c);
        }
    }
    cout << res.at(n - 1);
    return 0;
}