sjtu1285 时晴时雨

Description

Input Format

Output Format

Sample Input

Sample Output

这题是usedtobe大佬要我做的，他的dp比我的好写，我也不知道他写了什么。

考虑最后的方案肯定时晴雨天相

我的做法是这样的\(f[i][j][k]\)表示前\(i\)天，且最后一天是\(j\)天气(\(0\)晴天，\(1\)雨天)，且状态为\(k\)的方案数(\(0\)表示没有经历连续\(K\)个晴天，\(1\)表示已经经过了连续\(K\)个晴天，\(2\)表示已经经过了连续\(K\)个晴天和连续\(K\)个雨天)。

运用前缀和优化可以把复杂度优化到\(O(n)\)，转移脑补吧。

#include<iostream>

#include<cmath>

#include<cstdio>

#include<cstdlib>

using namespace std;

#define rhl (1000000007)

#define maxn (1000010)

int ans,N,K,f[maxn][2][3],pre[2][maxn]; char s[maxn];  //f[i][j][k]表示长度为i，最后一个是j(0\1),切当前状态为k的方案数

inline void upd(int &x) { if (x < 0) x += rhl; if (x >= rhl) x -= rhl; }

int main()

{

	freopen("1285.in","r",stdin);

	freopen("1285.out","w",stdout);

	scanf("%d %d\n",&N,&K); scanf("%s",s+1);

	for (int i = 1;i <= N;++i)

	{

		if (s[i] == 'B') pre[0][i] = i;

		else if (s[i] == 'W') pre[1][i] = i;

		pre[0][i] = max(pre[0][i],pre[0][i-1]);

		pre[1][i] = max(pre[1][i],pre[1][i-1]);

	}

	f[0][0][0] = f[0][1][0] = 1;

	for (int i = 1,l1,l2,mx;i <= N;++i) //枚举位置

	{

		for (int p = 0,q = 1;p < 2;++p,q ^= 1)

		{

			if (p == 0&&s[i] == 'W') continue;

			if (p == 1&&s[i] == 'B') continue;

			l1 = i-K+1; l2 = pre[q][i]; mx = max(l1,l2);

			//无长度拓展

			for (int k = 0;k < 3;++k)

			{

				f[i][p][k] += f[i-1][q][k];

				if (mx) f[i][p][k] -= f[mx-1][q][k];

				upd(f[i][p][k]);

			}

			//有长度拓展

			if (l1&&l1 >= l2)

			{

				//k == 0

				if (p == 1)

				{

					f[i][p][0] += f[l1-1][q][0];

					if (l2) f[i][p][0] -= f[l2-1][q][0];

					upd(f[i][p][0]);

				}

				//k == 1

				if (p == 0)

				{

					f[i][p][1] += f[l1-1][q][0];

					if (l2) f[i][p][1] -= f[l2-1][q][0];

					upd(f[i][p][1]);

					f[i][p][1] += f[l1-1][q][1];

					if (l2) f[i][p][1] -= f[l2-1][q][1];

					upd(f[i][p][1]);

				}

				//k == 2

				if (p == 0)

				{

					f[i][p][2] += f[l1-1][q][2];

					if (l2) f[i][p][2] -= f[l2-1][q][2];

					upd(f[i][p][2]);

				}

				else

				{

					f[i][p][2] += f[l1-1][q][1];

					if (l2) f[i][p][2] -= f[l2-1][q][1];

					upd(f[i][p][2]);

					f[i][p][2] += f[l1-1][q][2];

					if (l2) f[i][p][2] -= f[l2-1][q][2];

					upd(f[i][p][2]);

				}

			}

		}

		for (int j = 0;j < 3;++j)

		{

			f[i][0][j] += f[i-1][0][j]; f[i][1][j] += f[i-1][1][j];

			upd(f[i][0][j]); upd(f[i][1][j]);

		}

	}

	ans = f[N][0][2]+f[N][1][2]-f[N-1][0][2]-f[N-1][1][2]; upd(ans);

	printf("%d",ans);

	fclose(stdin); fclose(stdout);

	return 0;

}