【Codeforces】CF 2005 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 $scor{e}_n-scor{e}_c$, where $scor{e}_n$ is Narek’s score and $scor{e}_c$ is ChatGPT’s score.

Narek calculates $scor{e}_n$ by examining the selected string (he moves from left to right). He initially searches for the letter $\text{"n"}$, followed by $\text{"a"}$, $\text{"r"}$, $\text{"e"}$, and $\text{"k"}$. Upon finding all occurrences of these letters, he increments $scor{e}_n$ by $5$ and resumes searching for $\text{"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 $scor{e}_c$ by $1$ for each letter $\text{"n"}$, $\text{"a"}$, $\text{"r"}$, $\text{"e"}$, or $\text{"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 $scor{e}_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 $scor{e}_n-scor{e}_c$ by selecting the most optimal subset of the initial strings.

输入格式

In the first line of the input, you’re given a single integer $t$ ($1\le t\le 10^5$), the number of test cases. Then the description of each test case follows.

In the first line of each test case, you’re given two integers $n,m$ ($1\le n,m\le 10^3$), the number of strings and the length of each string.

In the next $n$ lines, you’re given $n$ strings, each having a length of $m$. The strings only contain lowercase letters of the English alphabet.

The sum of values of $n\cdot m$ over all test cases does not exceed $10^6$.

输出格式

For each test case, output a single integer: the maximal possible value of $scor{e}_n-scor{e}_c$.

样例 #1

样例输入 #1

4
5 2
nn
aa
rr
ee
kk
1 5
narek
1 4
nare
5 7
nrrarek
nrnekan
uuuuuuu
ppppppp
nkarekz

样例输出 #1

0
5
0
7

解法

解题思路

首先每个字符串都有选择和不选择的两种方式，但是，如果选择了这个字符串，那么一定会选择它的所有匹配的子串。 因此，对于前者，我们使用动态规划，而对于动态规划中的子问题，则是直接使用贪心来匹配子串。

因为每次匹配，最后可能会以$[n,a,r,e,k]$中其中一个结尾，因此设计动态规划状态为$f_{i,j}$，表示选择第$i$个字符串的时候，以$narek$的第$j$个字符结束。

注意这里的 j = { 0 , 1 , 2 , 3 , 4 } j = \{0,1,2,3,4\} j={0,1,2,3,4}分别对应以 { k , n , a , r , e } \{k,n,a,r,e\} {k,n,a,r,e}结尾。

那么显然有以下的转移：
{ f i , j = max ⁡ ( f i , j , f i − 1 , j )    j ∈ { 0 , 1 , 2 , 3 , 4 } f i , k = max ⁡ ( f i , k , f i − 1 , j   + s u m j k )    j , k ∈ { 0 , 1 , 2 , 3 , 4 } \begin{cases} f_{i,j} = \max(f_{i,j},f_{i-1,j} ) \ \ j \in\{0,1,2,3,4\} \\ f_{i,k} = \max(f_{i,k},f_{i-1,j} \ +sum_j^k ) \ \ j,k \in \{0,1,2,3,4\} \end{cases} {fi,j​=max(fi,j​,fi−1,j​)  j∈{0,1,2,3,4}fi,k​=max(fi,k​,fi−1,j​ +sumjk​)  j,k∈{0,1,2,3,4}​

其中$su{m}_j^k$表示贪心地从$j$结尾的字符开始选，选到$k$结尾的字符获得的贡献。

最后，我们计算答案的时候，要减去不完整的部分的贡献，比如我们选择答案以$j=3$，即$r$结尾，那么答案贡献需要减去$3$，因为要丢掉$rek$这三个贡献，并且加到$GPT$上。

所以答案为${\max }_{j=0}^{j\le 4}(f_{n,j}-j)$

代码

const int N = 1e3 + 10;
 
int f[N][5];
std::string t = "narek";
void solve() {
	int n, m;
	std::cin >> n >> m;
 
	std::vector<std::string>a(n + 1);
	for (int i = 1; i <= n; ++i) {
		std::cin >> a[i];
	}
 
	memset(f, -0x3f, sizeof(f));
 
	f[0][0] = 0;
	for (int i = 1; i <= n; ++i) {
		for (int j = 0; j < 5; ++j) {
			int k = j, res = f[i - 1][j];
			for (auto& c : a[i]) {
				if (c == t[k]) {
					++k;
					if (k == 5) {
						res += 5;
						k = 0;
					}
				}
				else if (t.find(c) != std::string::npos) {
					--res;
				}
			}
			f[i][k] = std::max(f[i][k], res);
		}
		for (int j = 0; j < 5; ++j) {
			f[i][j] = std::max(f[i][j], f[i - 1][j]);
		}
	}
 
 
	int res = 0;
	for (int i = 0; i < 5; i++) {
		res = std::max(res, f[n][i] - i);
	}
	std::cout << res << "\n";
 
}
 
signed main() {
	std::ios::sync_with_stdio(0);
	std::cin.tie(0);
	std::cout.tie(0);
 
	int t = 1;
	std::cin >> t;
 
	while (t--) {
		solve();
	}
}