nico和niconiconi

难度：3星

计 $dp[i]dp[i]$ 代表前 $ii$ 个字符的计数最大值。

那么可得转移方程：

若取当前子串"nico"：

$if(substring(i-3,i)==nico)thenif(substring(i-3,i)==nico)then$ $dp[i]=max(dp[i],dp[i-4]+a)dp[i]=max(dp[i],dp[i-4]+a)$

若取当前子串"niconi"：

$if(substring(i-5,i)==niconi)thenif(substring(i-5,i)==niconi)then$ $dp[i]=max(dp[i],dp[i-6]+b)dp[i]=max(dp[i],dp[i-6]+b)$

若取当前子串"niconiconi"：

$if(substring(i-9,i)==niconiconi)thenif(substring(i-9,i)==niconiconi)then$ $dp[i]=max(dp[i],dp[i-10]+c)dp[i]=max(dp[i],dp[i-10]+c)$

最后输出 $dp[n]dp[n]$ 即可。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll dp[322222]={0};
string a;
int main(){

    ll i,n,x,y,z;
    cin>>n>>x>>y>>z;
    cin>>a;
    for(i=0;i<n;i++){
        if(i>0)dp[i]=dp[i-1];
        if(i>=3&&a[i-3]=='n'&&a[i-2]=='i'&&a[i-1]=='c'&&a[i]=='o')
            dp[i]=max(dp[i],dp[i-3]+x);
        if(i>=5&&a[i-5]=='n'&&a[i-4]=='i'&&a[i-3]=='c'&&a[i-2]=='o'&&a[i-1]=='n'&&a[i]=='i')
            dp[i]=max(dp[i],dp[i-5]+y);
        if(i>=9&&a[i-9]=='n'&&a[i-8]=='i'&&a[i-7]=='c'&&a[i-6]=='o'&&a[i-5]=='n'&&a[i-4]=='i'&&a[i-3]=='c'&&a[i-2]=='o'&&a[i-1]=='n'&&a[i]=='i')
            dp[i]=max(dp[i],dp[i-9]+z);
    }
    //这里偷懒了，对于字符a[i]='n'的情况，显然dp[i]=dp[i-1]。这样就不用处理dp[-1]的值。
    cout<<dp[n-1];
}