“玲瓏杯”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) {