首先，想到贪心，但是比较缠，前后选取互相影响，贪心不可取，所以基本确定是dp，再加上数据范围比较小，给dp留下了操作空间，如果是贪心的话，那么基本上是扫一遍，O(n)的复杂度，所以更加确定是dp

如何dp呢？

按照以往背包的经验，选与不选，先写上第一维dp[i]表示在前i个中选择，结果则是和问题相对应，为scoren−scorec 的最大可能值，其中如果遇到顺序的narek，加5分，否则如果n，a，r，e，k不在narek中，则减1分，简化为，遇到n，a，r，e，k减1分，遇到顺序的narek加10分，那么dp[i]则表示分数的最大值

但是一维远远不够，因为要和narek去匹配，所以再加一维，就是匹配到了narek的第几个字符 （加的这一维根据多出来的信息去加，比如该题额外的信息是和nerek这长度为5的字符串去匹配，那么第二维长度为5，再比如背包问题问背包为m的最多可以装多少重量的物品，那么第二维长度为m）

dp[i][j]表示在前i个字符串里选择,当前匹配到"narek"的第j个字符获得的最大分数
//不选
for(int j=0;j<5;j++) dp[i][j]=max(dp[i][j],dp[i-1][j]);
//选
for(int j=0;j<5;j++){dp[i][nxt]=max(dp[i][nxt],dp[i-1][j]+score);//在已经匹配了第j个字符的基础上,选了第i个字符串后,匹配到了第nxt个字符,获得了分数score
}

初始化也是一个难点：

初始化最后的时候再写，根据我们的循环第一次需要什么状态，作为一个启动源

除了启动源之外，如果是求最大，那么全初始化为很大的正数，如果是求最小，那么全初始化为很小的负数

i=1,j=0
dp[1][0]=max(dp[1][0],dp[0][0]);
dp[1][nxt(0)]=max(dp[1][nxt(0)],dp[0][0]+score(0));
//分析
其中,nxt(0)可能是[0,4]中的任何一个,score也不定,可能为正数,也可能为负数
首先,我们需要dp[0][0]作为前一状态转移到后一状态,目前状态为匹配到了第0个字符,也就是说目前什么也没匹配,那么dp[0][0]+score作为dp[1][nxt(0)]的分数,应该就是score,所以dp[0][0]需要初始化为0

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
typedef pair<int,int>PII;
const int N=1010;
int dp[N][10];
int n,m;
string tmp="narek";
PII f(string s,int now){int score=0;for(int i=0;i<(int)s.size();i++){if(tmp.find(s[i])!=tmp.npos) score--;if(s[i]==tmp[now]) {now++;if(now==5){score+=10;now=0;}}}return {score,now};
}
void solve() {cin>>n>>m;for(int i=0;i<=n;i++){for(int j=0;j<5;j++){dp[i][j]=-2e9;}}dp[0][0]=0;for(int i=1;i<=n;i++){string s;cin>>s;for(int j=0;j<5;j++) {dp[i][j]=max(dp[i][j],dp[i-1][j]);//不选PII t=f(s,j);int score=t.first,nxt=t.second;dp[i][nxt]=max(dp[i][nxt],dp[i-1][j]+score);}}int ans=0;for(int j=0;j<5;j++){ans=max(ans,dp[n][j]);}cout<<ans<<endl;
}
signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t=1;cin>>t;while(t--) {solve();}return 0;
}