寫在前面????

這道題我有在網上去搜尋了一下其他部落客的題解，因為我實在無法了解 d p [ i ] = d p [ i − 1 ] ⋅ 2 + d p [ i − 3 ] dp[i] = dp[i-1]\cdot2+dp[i-3] dp[i]=dp[i−1]⋅2+dp[i−3] 這個狀态轉移方程是如何得到的（可能是自己太笨了），他們的題解大多都是草草兩句收尾講的有些含糊不清，作為菜狗的我真的很難懂啊啊啊啊！在思考良久後對于這道題我想到了一種自己的解題想法，與網上主流的狀态轉移方程不同不過同樣能夠解題。

藍橋杯????2022年第十三屆省賽真題-積木畫

時間限制: 1Sec 記憶體限制: 256MB 送出: 623 解決: 135

題目描述

小明最近迷上了積木畫，有這麼兩種類型的積木，分别為 I 型（大小為 2 個機關面積）和 L 型（大小為 3 個機關面積）：

同時，小明有一塊面積大小為 2 × N 的畫布，畫布由 2 × N 個 1 × 1 區域構成。小明需要用以上兩種積木将畫布拼滿，他想知道總共有多少種不同的方式？ 積木可以任意旋轉，且畫布的方向固定。

輸入

輸入一個整數 N，表示畫布大小。

輸出

輸出一個整數表示答案。由于答案可能很大，是以輸出其對 1000000007 取模後的值。

樣例輸入複制

3      

樣例輸出複制

5      

提示

五種情況如下圖所示，顔色隻是為了辨別不同的積木：

對于所有測試用例，1 ≤ N ≤ 10000000.

解題思路1️⃣:

哎，但凡是比賽的時候再測一個資料也不會不過，太可惜了，但是寫的時候思路是對的，可惜a[2][1]寫錯了。

思路：a[i][0]:i列積木的堆法，a[i][1]：i列多一塊小方格的堆法。

如：

或者

不管這三塊是怎麼放的，都叫a[3][0].

如果在此基礎上右邊多一個小方格就叫a[3][1]，注意小方格可以在第四列上一行也可以在第四列下一行（不好找圖就不給了，自行想象）

給出動态規劃方程：

[i][0]=(a[i-2][0]+a[i-2][1]+a[i-1][0])%mod; 
a[i][1]=(a[i-1][0]*2+a[i-1][1])%mod;      

畫布大小為i的排法，既a[i][0]的值：

1. 先考慮少一塊I型積木的排法，既a[i-1][0],這時加上一塊I型積木就行了，
2. 再考慮少一塊L型積木的排法，既a[i-2][1],這時加上一塊L型積木就行了,
3. 考慮少兩塊I型積木的排法，既a[i-2][0]，加上兩塊I型積木，注意，兩塊必需橫着加進去，如果是豎着加，就相當于第一種類型排法了，重複了。
4. 涉及缺更多積木時，會發現無論怎麼排，排法都會和上述情況重複,也就是說，以上三種情況涵蓋了a[i][0]的所有排法。

是以有：

a[i][0]=(a[i-2][0]+a[i-2][1]+a[i-1][0])%mod;      

a[i][1]的排法，大家可以自行畫圖寫出來。

寫出初始狀态：

a[1][0]=1,a[2][0]=2,a[1][1]=2,a[2][1]=4;      

????給出完整代碼：

#include<stdio.h>
#define mod 1000000007
long int a[10000001][2];
int main()
{
     int n;
    a[1][0]=1,a[2][0]=2,a[1][1]=2,a[2][1]=4;
    scanf("%d",&n);
    if(n==1)printf("1");
    else if(n==2)printf("2");
    else {
        for(int i=3;i<=n;i++){
            a[i][0]=(a[i-2][0]+a[i-2][1]+a[i-1][0])%mod;
            a[i][1]=(a[i-1][0]*2+a[i-1][1])%mod;
        }
        printf("%ld",a[n][0]%mod);
    }
    return 0;
}      

解體思路2️⃣：

首先這個題肯定是用動态規劃來做的,正好它也符合動态規劃做題的思想,無後效性也滿足是以我們用動态規劃做會好做一點.

那怎麼想這個題呢,首先它是二維的一個矩陣模式,并且有擺放還是有順序的,是以我們如果要用二維dp來做還确實不好做,拿我們所幸直接用一維來簡化拼積木的過程,但是怎麼簡化呢.

我們先來看下題目給的案例:

首先我們直接來看三階的,第一個和第二個我們可以發現I型積木拼放的方式是有2種的,或者看一和四都行,然後L型積木的拼接方式是1種看三和五(你把他們兩個反轉過來就是一種),那我們不妨想的簡單一點是以遞推公式就是:dp[i]=dp[i-1]*2+dp[i-3];

證明的方法就是我們剛才的思想過程,我們講二維的矩陣看成了一維的,是以I型積木就是等于1個方格,是以我們記為i-1,L型積木就是等于1.5個方格,但是L型積木不能單獨出現,必須成雙的出現,是以我們記為i-3,又由于I型積木出現在一個位置有兩種方式,是以我們乘以二,L型積木出現隻有一直方式我們乘以1,就結束了。

但是我們還要進行初始化前三個:

當i等于1的時候dp就是1,這個沒啥說的,隻能放一種I型不管咋放都一樣.

當i等于2的時候dp是2,因為可以放兩個I型,可以水準放可以豎直放2種.

當i等于3的時候就是題目當中的情況dp等于5,

????參考代碼:

#include<stdio.h>
#include<string.h>
#define mod 1000000007
int dp[10000005];
int main()
{
    int n;
    scanf("%d",&n);
    memset(dp,0,sizeof(dp));
    dp[1]=1,dp[2]=2,dp[3]=5;
    for(int i=4;i<=n;i++)
    {
        dp[i]=(dp[i-1]*2%mod+dp[i-3]%mod)%mod;
    }
    printf("%d\n",dp[n]);
    return 0;
}      

解題思路3️⃣：

狀态表示

本題解題的關鍵是使用動态規劃，定義一維數組 d p dp dp ， d p [ i ] dp[i] dp[i] 存儲畫布的大小為 2 × i 2\times i 2×i 時積木的填充方法數。

狀态初始化

不難發現：

• 當畫布大小為 2 × 1 2\times 1 2×1 時，隻能放下一個 I 型積木，是以 d p [ 1 ] = 1 dp[1] =1 dp[1]=1。

• 當畫布大小為 2 × 2 2\times 2 2×2 時，隻能放下兩個 I 型積木，但積木可以旋轉,如下圖所示，是以 d p [ 2 ] = 2 dp[2] = 2 dp[2]=2





• 當畫布大小為 2 × 3 2\times3 2×3時，如題目中所示，共有五種方式，是以 d p [ 3 ] = 5 dp[3] = 5 dp[3]=5

情況梳理

梳理狀态轉移方程之前，不妨思考下，積木畫出現在最後且符合題意的積木塊隻能出現哪幾種情況呢？

• 情況一：單獨使用 I 型積木拼接

  完全可以使用單獨的

  

  拼接在任意一個符合題意的積木畫尾部中，使積木畫總長度 + 1。

• 情況二：使用兩個 I 型積木拼接

  使用

  

  同樣能夠拼接到任意一個符合題意的積木畫尾部，使其積木畫總長度 + 2。

• 情況三：使用兩個 L 型積木拼接

  使用

  

  或

  

  拼接到任意一個符合題意的積木畫尾部，使其積木畫總長度 +3，但要注意此時存在這兩種 L 型積木拼接方式屬于不同的方式，是以需要單獨計算！

• 情況四：使用兩個 L 型積木與 i ( 1 , 2 , 3 , . . . . n ) i(1,2,3,…n) i(1,2,3,…n) 個 I 型積木拼接

  最容易被忽略的情況！使用 I 型積木與 兩個 L 型積木同樣能完成拼接。



• 不要忘記翻轉後的情況：

狀态轉移方程

• 情況一：單獨使用 I 型積木拼接， d p [ i ] + = d p [ i − 1 ] dp[i] += dp[i-1] dp[i]+=dp[i−1]
• 情況二：使用兩個 I 型積木拼接， d p [ i ] + = d p [ i − 2 ] dp[i]+=dp[i-2] dp[i]+=dp[i−2]
• 情況三：使用兩個 L 型積木拼接， d p [ i ] + = 2 ⋅ d p [ i − 3 ] dp[i]+=2\cdot dp[i-3] dp[i]+=2⋅dp[i−3]
• 情況四：情況四隻有 i > = 4 i>=4 i>=4 時才可能出現，具體讨論如下：
• 若 i = = 4 i4 i4 ，隻存在長度為 4 的拼接情況，假設 d p [ 0 ] = 1 dp[0]=1 dp[0]=1，也就是說 d p [ 4 ] + = d p [ 0 ] ⋅ 2 dp[4]+=dp[0]\cdot 2 dp[4]+=dp[0]⋅2
• 若 i = = 5 i5 i5，存在長度為 4 , 5 4,5 4,5 的拼接情況，即 d p [ 5 ] + = ( d p [ 0 ] + d p [ 1 ] ) ⋅ 2 dp[5] += (dp[0]+dp[1])\cdot 2 dp[5]+=(dp[0]+dp[1])⋅2
• 若 i = = 6 i 6 i6，繼續推導有： d p [ 6 ] + = ( d p [ 0 ] + d p [ 1 ] + d p [ 2 ] ) ⋅ 2 dp[6]+=(dp[0]+dp[1]+dp[2])\cdot 2 dp[6]+=(dp[0]+dp[1]+dp[2])⋅2
• 若 i = = 7 i7 i7，推導有： d p [ 7 ] + = ( d p [ 0 ] + d p [ 1 ] + d p [ 2 ] + d p [ 3 ] ) ⋅ 2 dp[7]+=(dp[0]+dp[1]+dp[2]+dp[3])\cdot 2 dp[7]+=(dp[0]+dp[1]+dp[2]+dp[3])⋅2

按照上述推導，不難發現 d p [ i ] + = ( d p [ 0 , 1 , 2 , . . . , i − 4 ] ) ⋅ 2 dp[i]+=(dp[0,1,2,…,i-4])\cdot 2 dp[i]+=(dp[0,1,2,…,i−4])⋅2，是以可以定義一個變量 s u m sum sum 存儲 d p [ 0 , 1 , 2 , . . i ] dp[0,1,2,…i] dp[0,1,2,…i] 的值，在 i i i 增大的同時更新 s u m sum sum 的值，初始情況 s u m = 0 sum=0 sum=0。

傳回結果

最終 d p [ N ] dp[N] dp[N] 就是題目所求值，這道題就這樣解決了。

???? 代碼編寫

#include <iostream>
#include <math.h>
#define ll long long
// #include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000007;
int main() {
  ll n, a1, a2, a3;
  a1 = 5;
  a2 = 2;
  a3 = 1;
  cin >> n;
  ll sum = 0;
  for (ll i = 4; i <= n; ++i) {
    ll val = 0;
    val += a1;
    val += a2;
    val += (a3 * 2L);
    if (i >= 4) {
      val += sum * 2 + 2;
      sum += a3;
    }
    val %= MOD;
    a3 = a2;
    a2 = a1;
    a1 = val;
  }
  cout << a1;
  return 0;
}      

寫在最後????