CSES - Counting Towers (DP)

(Updated: )
算法 › DP

Counting Towers (DP)

题意

建造宽为$2$, 长为$n$的塔的堆砖方案数, 砖可以是任意长宽都为整数的.

题解

定义状态:$dp[i][1]$和$dp[i][0]$分别表示第$i$层是整体和两块砖的方案数.
状态转移:
只关注第$i$层是怎么构建的:

  1. 如果第$i$层是一块整体的, 那么:
  2. 如果$i-1$层是一块整体, 它可以是和$i-1$层分开的, 也可以是和$i-1$层合并的
  3. 如果$i-1$层是两块砖, 那么$i$层只可以是和$i-1$层分开的
  4. 所以$dp[i][1] = 2 * dp[i-1][1] + dp[i-1][0]$
  5. 如果第$i$层是两块砖, 那么:
  6. 如果$i-1$层是一块整体的, 那么第$i$层只能是和$i-1$层分开的
  7. 如果$i-1$层是两块砖, 那么考虑:
    1. 左合并, 右分开
    2. 右合并, 左分开
    3. 左分开, 右分开
    4. 左合并, 右合并
  8. 综上, $dp[i][0] = dp[i-1][1] + 4 * dp[i-1][0]$

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
  #include<bits/stdc++.h>
using namespace std;

#define DEBUG
#ifdef DEBUG
#define de(x) cout << (#x) << "=" << (x) << endl;
#define de2(x, y) cout << (#x) << " " << (#y) << " = " << (x) << " " << (y) << endl;
#else
#define de(x) 42
#define de2(x, y) 42
#endif
#define endl '\n'
#define fi(n) for(int i = 1;i <= n; ++i)
#define fi0(n) for(int i = 0;i < n; ++i)
#define fj(n) for(int j = 1;j <= n; ++j)
#define all(x) (x.begin(), x.end())
#define hello ios::sync_with_stdio(0); cin.tie(0);cout.tie(0);
#define world return 0;
#define int long long
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef long long ll;


const int N = 1e6 + 10;
const int M = 1e9 + 7;
int dp[N][2];
signed main() {
    int t; cin >> t;

    dp[1][0] = 1;dp[1][1] = 1;
    for(int i = 2; i < N; ++i) {
        dp[i][0] = (4 * dp[i-1][0] + dp[i-1][1]) % M;
        dp[i][1] = (2 * dp[i-1][1] + dp[i-1][0]) % M;
    }

    while(t--) {
        int n; cin >> n;
        cout << (dp[n][0] + dp[n][1]) % M << endl;

    }
}