“玲珑杯”ACM比赛 Round #10-A-Black and White

2019-11-08 02:43:04

字体：大中小

来源：转载

供稿：网友

ACM模版

描述

题解

这个问题是典型的 dp 问题，一开始害怕超时，后来仔细一想是 O(n) 复杂度，所以是可行的。

这里我们不用纠结于 a 黑 b 白还是 a 白 b 黑，因为结果都是一样的。索性用0、1表示更为容易表达。

dp[i][j]表示以第 i 个位置为 j 的情况数，j 为 0 或 1， sum[i][j]表示dp[1][j] + dp[2][j] + … + dp[n][j]。

状态的转移分为3段，所以这是分段 dp。首先，我们将 a、b 的值进行对比交换，保证 a 小于 b，至于为什么这样子对结果没有影响，前边已经说过了。然后我们可以考虑在前 a-1 段不会出现违规的排列，而 a 到 b-1 会出现0的违规，剩余的 b 到 n 阶段两种违规排列均可能出现，所以一共分为三段进行处理。

接着需要说明的便是 dp[i][j] 与 sum[i][j] 的关系，这两者的关系主要体现在违规时的处理，拿 0 来说，0 连续长度不能超过 a，所以可以存在 1 个 0 ， 2 个 0 ， 3 个 0 ，…，a-1 个 0 连续，我们反过来想，连续的 0 前面自然就是 1 ，所以我们也就可以得到如下状态转移方程：

`dp[i][0] = (sum[i - 1][1] - sum[i - a][1] + MOD) % MOD;`

1 的情况和 0 大同小异，无需多说了。

最后，不要忘了进行特判，因为存在整个序列只能为0或者1，或者不存在合法序列的情况。

代码

#include <cstdio>#include <algorithm>using namespace std;const int MOD = 1e9 + 7;const int MAXN = 1e6 + 5;int dp[MAXN][2]; // 0:Black 1:Writeint sum[MAXN][2];void init(){ dp[1][0] = dp[1][1] = 1; sum[1][0] = sum[1][1] = 1;}int main(){ int T; scanf("%d", &T); while (T--) { init(); int a, b, n; scanf("%d%d%d", &a, &b, &n); // a白、b黑等价于 a黑、b白 if (a > b) { swap(a, b); } if (a == 1) { if (b < n) { PRintf("0/n"); } else { printf("1/n"); } continue; } // 前 a-1 个不会出现违规排列 for (int i = 2; i < a; i++) { dp[i][1] = dp[i][0] = dp[i - 1][0] * 2 % MOD; sum[i][0] = (sum[i - 1][0] + dp[i][0]) % MOD; sum[i][1] = (sum[i - 1][1] + dp[i][1]) % MOD; } // a 到 b-1 只有一种会违规 for (int i = a; i < b; i++) { dp[i][0] = (sum[i - 1][1] - sum[i - a][1] + MOD) % MOD; dp[i][1] = (dp[i - 1][0] + dp[i - 1][1]) % MOD; sum[i][0] = (sum[i - 1][0] + dp[i][0]) % MOD; sum[i][1] = (sum[i - 1][1] + dp[i][1]) % MOD; } // b 到 n 两种违规可能 for (int i = b; i <= n; i++) { dp[i][0] = (sum[i - 1][1] - sum[i - a][1] + MOD) % MOD; dp[i][1] = (sum[i - 1][0] - sum[i - b][0] + MOD) % MOD; sum[i][0] = (sum[i - 1][0] + dp[i][0]) % MOD; sum[i][1] = (sum[i - 1][1] + dp[i][1]) % MOD; } printf("%d/n", (dp[n][0] + dp[n][1]) % MOD); } return 0;}

上一篇：【c语言】模拟实现strcat函数

下一篇：外观模式

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注