思路：
水解:O($n^2$)

考慮轉化問題，判斷合法性。
經過推理，我們得知每一個變量和上一個至多相差 1 。上一個變量是 2 的話，這一個只能取 3 或者 2 或者 1 。

題目可以轉化為這幅圖，a和b代表兩個確定高度，求：
從a開始，每次可以向右上/右/右下走，不能越過紫線，求到b點的方案數
因為相鄰兩塊積木的高度 如果相差超過 2 22 的話，無法構造。（這點應該清楚）

然后我們就可以DP 來計算方案數了。
設f[i][j] 表示 已經處理完前 i?1 個數之后，當前 第i 個數 選擇了j 高度 的合法方案數。
即按照它相鄰兩個數相差$\le 1$ 的性質，我們即可推出下列柿子：（當 $a_i=?1$ 時）
$$f[i][j]=f[i?1][j?1]+f[i?1][j]+f[i?1][j+1]$$
特別地，對于越界的訪問（比如 j=1 或者j=num[i?1] ）就不統計越界的答案。
$a_i>?1$時特判即可，不需要枚舉j 。
最后這個 f 數組還要取模。

#include <cstdio> #include <iostream> #include <cstring> #pragma GCC optimize(2) #define ll long long #define mod 1000000007using namespace std;const int N = 2e4 + 10; int n, t, tt; ll a[N], f[5][N];int h(int x) //求出當前點最大可能的高度 {if(x < n / 2 + 1) return x - 1;return n - x; }int main() {freopen("brick.in", "r", stdin);freopen("brick.out", "w", stdout);scanf("%d", &n);for(int i = 1; i <= n; i++) scanf("%lld", &a[i]);f[0][0] = 1;for(int i = 1; i <= n; i++){t = h(i);tt = h(i - 1);if(a[i] != -1){if(a[i] <= t){f[1][a[i]] += f[0][a[i]];if(a[i]> 0) f[1][a[i]] += f[0][a[i] - 1];if(a[i] < tt) f[1][a[i]] += f[0][a[i]+1];if(!(i % 10)) f[1][a[i]] %= mod; }}else{for(int j = 0; j <= t; j++){f[1][j] += f[0][j];if(j >= 1) f[1][j] += f[0][j - 1];if(j < tt) f[1][j] += f[0][j + 1];if(!(i % 10)) f[1][j] %= mod;}}memcpy(f[0], f[1], sizeof(f[1]));memset(f[1], 0, sizeof(f[1]));}printf("%lld\n", f[0][0] % mod);return 0; }

總結

以上是生活随笔為你收集整理的[gmoj 3505]【NOIP2013模拟11.4A组】积木的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。