C. Lazy Narek

题目

Narek is too lazy to create the third problem of this contest. His friend Artur suggests that he should use ChatGPT. ChatGPT creates $n$ problems, each consisting of $m$ letters, so Narek has $n$ strings. To make the problem harder, he combines the problems by selecting some of the $n$ strings possibly none and concatenating them without altering their order. His chance of solving the problem is defined as $score_n - score_c$, where $score_n$ is Narek’s score and $score_c$ is ChatGPT’s score.

Narek calculates $score_n$ by examining the selected string (he moves from left to right). He initially searches for the letter $\texttt{“n”}$, followed by $\texttt{“a”}$, $\texttt{“r”}$, $\texttt{“e”}$, and $\texttt{“k”}$. Upon finding all occurrences of these letters, he increments $score_n$ by $5$ and resumes searching for $\texttt{“n”}$ again (he doesn’t go back, and he just continues from where he left off).

After Narek finishes, ChatGPT scans through the array and increments $score_c$ by $1$ for each letter $\texttt{“n”}$, $\texttt{“a”}$, $\texttt{“r”}$, $\texttt{“e”}$, or $\texttt{“k”}$ that Narek fails to utilize (note that if Narek fails to complete the last occurrence by finding all of the $5$ letters, then all of the letters he used are counted in ChatGPT’s score $score_c$, and Narek doesn’t get any points if he doesn’t finish finding all the 5 letters).

Narek aims to maximize the value of $score_n - score_c$ by selecting the most optimal subset of the initial strings.

实现

定义dp[i] [j]为前i个字符串，最后一个字符串匹配到了j个字母（n–1,a–2,r–3,e–4,k–5），每一次更新当前字符串分别以前某个字符串需要的字母为开头开始计数，算出以这个字母开头的分数差，进行状态转移，最后在dp[n] [i]中枚举一下最优解减去i+1即为答案

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e3+10;
int a[N],b[N],ans;
int dp[N][6];
int sum[6],need[6];
map<char,bool>st;

string temp="?narek";
int n,m;
void init(string s){
    for(int i=1;i<=5;i++) sum[i]=0,need[i]=i;
    for(int i=1;i<=m;i++){
        if(st[s[i]]){
            for(int j=1;j<=5;j++){
                if(s[i]==temp[need[j]]){
                    need[j]++;
                    if(need[j]==6) sum[j]+=5,need[j]=1;
                }
                else sum[j]--;
            }
        }
    }
}
void solve()
{
    cin>>n>>m;
    for(int i=0;i<=n;i++){
        for(int j=1;j<=6;j++){
            dp[i][j]=-1e4;
        }
    }
    dp[0][1]=0;
    for(int i=1;i<=n;i++){
        string s;
        cin>>s;
        s=' '+s;
        init(s);
        for(int j=1;j<=5;j++) dp[i][j]=dp[i-1][j];
        for(int j=1;j<=5;j++) dp[i][need[j]]=max(dp[i][need[j]],dp[i-1][j]+sum[j]);
    }
    int ans=0;
    for(int i=1;i<=5;i++){
        ans=max(ans,dp[n][i]-i+1);
    }
    cout<<ans<<endl;
}
signed main()
{
    st['n']=1,st['a']=1,st['r']=1,st['e']=1,st['k']=1;
    int t=1;
    cin>>t;
    while(t--)
    {
        solve();
    }
}