描述

给定三个字符串"nico","niconi","niconiconi",分别对应价值$a,b,ca,b,c$a,b,c，同时给定一个长度为$nn$n的字符串，选择该字符串中部分子串使得选择的子串的价值最大，每个字符仅能被选一次

思路

• 动态规划问题，设$dp\left[n\right]dp[n]$dp[n]为子串$[1,n][1,n]$[1,n]的最大价值，当前字符串为$ss$s，则有

dp[i]=⎩⎪⎨⎪⎧​dp[i−3]+adp[i−6]+bdp[i−10]+c​s[i−2:i]=="nico"s[i−5:i]=="niconi"s[i−9:i]=="niconiconi"​

• 最终答案为$dp\left[n\right]dp[n]$dp[n]

• 实现上可能利用数组/vector来实现会比较简洁，直接按照递推公式来写可能会容易出错，主要看个人喜好

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=3e5+5;
const string nico="nico";
const string niconi="niconi";
const string niconiconi="niconiconi";
char s[MAXN];
ll dp[MAXN];
int score[3];
int main()
{
    vector<string> v;
    v.push_back(nico);
    v.push_back(niconi);
    v.push_back(niconiconi);
    int n;
    scanf("%d%d%d%d",&n,&score[0],&score[1],&score[2]);
    scanf("%s",s+1);
    for(int i=1;i<=n;i++)
    {
        dp[i]=dp[i-1];
        for(int j=0;j<3;j++)
        {
            int len=v[j].size();
            if(i-len+1<=0)
                continue;
            bool flag=true;
            for(int k=0;k<len;k++)
                if(s[i-len+k+1]!=v[j][k])
                    flag=false;
            if(flag)
                dp[i]=max(dp[i],dp[i-len]+score[j]);
        }
    }
    printf("%lld",dp[n]);
}

时间复杂度$O\left(n\right)O(n)$O(n)，空间复杂度$O\left(n\right)O(n)$O(n)