Slash --- 字符串DP

#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#include 
#include 
#include 
using namespace std;
#define int long long
const int N = 110;
int f[N][N][N];
char g[N][N];
int res[N][N];
signed main()
{
	int n, m, len; cin >> n >> m;
	
	string s; cin >> s; len = s.size(); s = " " + s;
	for(int i = 1; i <= n; i ++) scanf("%s", g[i] + 1);
	
	memset(f, -1, sizeof f);
	memset(res, -1, sizeof res);
	
	for(int i = 1; i <= n; i ++)
	{
		for(int j = 1; j <= m; j ++)
		{
			for(int k = 1; k <= len; k ++)
			{
				if(g[i][j] != s[k]) continue;
				if(k == 1) f[i][j][k] = max({0ll, res[i - 1][j], res[i][j - 1]});
				else f[i][j][k] = max({f[i][j][k], f[i - 1][j][k - 1], f[i][j - 1][k - 1]});
				if(k == len) f[i][j][k] ++;
			} 
			res[i][j] = max({f[i][j][len], res[i - 1][j], res[i][j - 1]});
		}
	}
	cout << res[n][m] << '\n';
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37