坑点:字符串下标从1开始时,0这个位置可以随便转移的,1这个位置,在
s[i][j] == str[1]
的时候,也是可以转移的。(这地方调到结束也没调出来)
其他就是一个标准的数字三角形模型了,不断维护最大值即可
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<string, int> PSI;
const int N = 110, M = 2 * N;
const int mod = 998244353;
const int MOD = 1e9 + 7;
char str[N];
int n, m;
char s[N][N];
int f[N][N][N]; // 表示此状态能否继续向下转移
int dp[N][N][N]; // 表示 走到(i, j)此时 s[i][j]是str[k]的时候,最多组成多少个
signed main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n >> m;
cin >> str + 1;
int len = strlen(str + 1);
for (int i = 1; i <= n; i ++) {
for (int j = 1; j <= m; j ++) {
cin >> s[i][j];
}
}
for (int i = 0; i <= n; i ++) {
for (int j = 0; j <= m; j ++) {
f[i][j][0] = 1;
}
}
int res = 0;
for (int i = 1; i <= n; i ++) {
for (int j = 1; j <= m; j ++) {
for (int k = 0; k <= len; k ++) { // 首先0这个地方是可以随便转移的
dp[i][j][0] = max({dp[i][j][0], dp[i - 1][j][k], dp[i][j - 1][k]});
res = max(res, dp[i][j][0]);
}
if (s[i][j] == str[1]) { // 坑点,如果相等,1这个位置也是可以随便转移的
for (int k = 0; k <= len; k ++) {
f[i][j][1] = 1;
dp[i][j][1] = max({dp[i][j][1], dp[i - 1][j][k], dp[i][j - 1][k]});
}
if (len == 1) dp[i][j][1] ++;
res = max(res, dp[i][j][1]);
}
for (int k = 2; k <= len; k ++) { // 正常状态转移,从左面或者上面转移过来,如果此位置和最后一个位置相等,那就又多组成一个
if (f[i - 1][j][k - 1] == 1 && str[k] == s[i][j]) {
f[i][j][k] = 1;
dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j][k - 1]);
if (k == len) dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j][k - 1] + 1);
}
if (f[i][j - 1][k - 1] == 1 && str[k] == s[i][j]) {
f[i][j][k] = 1;
dp[i][j][k] = max(dp[i][j][k], dp[i][j - 1][k - 1]);
if (k == len) dp[i][j][k] = max(dp[i][j][k], dp[i][j - 1][k - 1] + 1);
}
res = max(res, dp[i][j][k]);
}
}
}
cout << res << '\n';
return 0;
}