关于滚动数组(玄关)
查看原帖
关于滚动数组(玄关)
982518
sjwhsss楼主2025/7/28 16:01

这道题要用滚动数组优化,我用 33 层差分数组表示 i1,i,i+1i-1,i,i+1 三层,如果直接在遍历 j,kj,k 转移并且已经转移完了后清空第 i1i-1 层,会WA,把 j,kj,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;
} 
2025/7/28 16:01
加载中...