这道题要用滚动数组优化,我用 3 层差分数组表示 i−1,i,i+1 三层,如果直接在遍历 j,k 转移并且已经转移完了后清空第 i−1 层,会WA,把 j,k 转移完后再遍历一次清空就没问题,我认为自己的滚动数组(应该)是没错的,有没有大佬看下我哪里错了?
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3+5 , maxm = 2e2+5 , mod = 1e9+7;
int n , m , K , dp[maxn][maxm] , ans , d[3][maxm][maxm];
char a[maxn] , b[maxm];
int roll(int x){return x%3;}
int main ()
{
ios::sync_with_stdio(),cin.tie(0),cout.tie(0);
cin >> n >> m >> K;
cin >> a + 1 >> b + 1;
for (int i = 1; i <= n; i++)
{
if (a[i] == b[1])dp[1][1]++;
for (int j = m; j; j--)
{
for (int k = K; k; k--)
{
d[roll(i)][j][k]+=d[roll(i-1)][j][k];
d[roll(i)][j][k]%=mod;
dp[j][k]+=d[roll(i)][j][k];
dp[j][k]%=mod;
if (a[i] == b[j])dp[j+1][k]+=dp[j][k],dp[j+1][k]%=mod;
else
{
dp[j][k]=0;
continue;
}
if (j == m && k == K)ans=(ans+dp[j][k])%mod;
d[roll(i+1)][j+1][k+1]=dp[j][k];
d[roll(i+1)][j+1][k+1]%=mod;
dp[j][k]=0;
//d[roll(i-1)][j][k]=0; //这里清空就会WA
}
}
for (int j = 1; j <= m; j++) for (int k = 1; k <= K; k++)d[roll(i-1)][j][k]=0; //这里就不会
}
cout << ans << "\n";
return 0;
}