C. Lazy Narek
思路:
动态规划 dp
dp[i] 表示 目前寻找的字符下标为i 时的最大分数(<=i<=4)
从前往后遍历字符串,每个字符串找5次,找完后把dp取max
注意找的过程中不能修改原dp数组,因为这5次查找是并行的,期间用ndp保存分数,找完了再修改dp (被数组的复制引用坑麻了,debug了半天)
详见注释
代码:
#include <bits/stdc++.h>
#define endl '\n'
#define int long long
#define pb push_back
#define pii pair<int,int>
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
typedef long long ll;
using namespace std;void solve() {const string ss = "narek";string s[10005];int n, m;cin >> n >> m;for (int i = 0; i < n; i++) {cin >> s[i];}int dp[5] = {0, -INF, -INF, -INF, -INF};//dp初始化为很小的数, dp[0]要初始化为0,是没有选择任何字符串的情况for (int i = 0; i < n; i++) {int ndp[5]; //临时保存dp下一状态的值copy(dp, dp + 5, ndp);for (int j = 0; j < 5; j++) {int fs = dp[j]; //当前状态的分数int nc = j; //当前在narek中的位置for (auto c : s[i]) {if (c == ss[nc]) { //如果字符匹配nc++;if (nc == 5) {fs += 5;nc = 0;}} else if (ss.find(c) != -1) { //不匹配fs--;}}ndp[nc] = max(ndp[nc], fs);}copy(ndp, ndp + 5, dp);// for(int i=0;i<5;i++)
// cout<<"=dp["<<i<<"] = "<<dp[i]<<endl;}int ans = 0;for (int i = 0; i < 5; i++) {ans = max(ans, dp[i] - i); //这里减去i是为了减去最后查找中断的narek的分数}cout << ans << endl;
}signed main() {cin.tie(0)->ios::sync_with_stdio(0);int T = 1;cin >> T;while (T--) {solve();}return 0;
}