Codeforces 182E - Wooden Fence 多阶段决策dp

传送门：https://codeforces.com/problemset/problem/182/E

题意

有n种木板，长为$a_i$，宽为$b_i$，当木板旋转时等于之前，则算一种木板，否则算不同类型。 这些木板有无数块，问，能组成多少个长为L的木板。求出方案数。

每种木板的长和宽都能作为“长”。

规则：

  • 当前选择的木板不能和前一种是同样类型
  • 当前选择的木板，长要等于上一块的宽。

思路

先看数据量，n=100，L=3000，DP！

如何选取状态？首先一定要遍历每块木板，则一个状态给遍历到第几块木板。

如果放下一块木板之后，它的总长会发生变化，而且需要上一个状态的总长。 则当前的总长需要记录，给一个状态给长度。

这块木板是横着放，还是竖着放？上一块是横还是竖？而且必须是长等于上一个宽。 所以需要一个状态记录当前块要怎么放？并且通过上一个木块怎么放来转移。

因此，我们得到dp[i][j][0/1]，表示放入第j块之后，长度为i，并且第j快是1（宽放）｜0（长放）。

如何转移？

需要通过前一块的状态来进行转移：

1
2
3
4
5
6
7
8
if(a[j] == a[k] && i > a[j] && dp[i - a[j]][k][1]) 
    dp[i][j][0] = (dp[i][j][0] + dp[i - a[j]][k][1]) % mod;
if(a[j] == b[k] && i > a[j] && a[k] != b[k] && dp[i - a[j]][k][0]) 
    dp[i][j][0] = (dp[i][j][0] + dp[i - a[j]][k][0]) % mod;
if(b[j] == b[k] && i > b[j] && dp[i - b[j]][k][0]) 
    dp[i][j][1] = (dp[i][j][1] + dp[i - b[j]][k][0]) % mod;
if(b[j] == a[k] && i > b[j] && a[k] != b[k] && dp[i - b[j]][k][1]) 
    dp[i][j][1] = (dp[i][j][1] + dp[i - b[j]][k][1]) % mod;

这里的a[k]!=b[k]，就是避免连续两块类型相同。

看上一块的横放还是竖放，来转移当前块是横放还是竖放。

复杂度为$O(n*n*L)$

Code

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
44
45
46
##include "bits/stdc++.h"
using namespace std;

typedef long long ll;

// const ll mod = 998244353;
const ll mod = 1e9 + 7;

const int N = 3005;
ll dp[N][N][2]; // dp[i][j][0/1] 长度为i，用到第j个board，长0，宽1

void solve() {
    int n, L; cin >> n >> L;
    vector<int> a(n + 1), b(n + 1);
    for(int i = 1;i <= n; i++) cin >> a[i] >> b[i];
    for(int i = 1;i <= L; i++) {
        for(int j = 1;j <= n; j++) {
            if(a[j] == i) dp[i][j][0]++;
            if(b[j] == i) dp[i][j][1]++;
        }
    }
    for(int i = 1;i <= L; i++) {
        for(int j = 1;j <= n; j++) { // 当前的第j个
            for(int k = 1;k <= n; k++) { // 之前的第k个比较
                if(j == k) continue;
                if(a[j] == a[k] && i > a[j] && dp[i - a[j]][k][1])
                    dp[i][j][0] = (dp[i][j][0] + dp[i - a[j]][k][1]) % mod;
                if(a[j] == b[k] && i > a[j] && a[k] != b[k] && dp[i - a[j]][k][0])
                    dp[i][j][0] = (dp[i][j][0] + dp[i - a[j]][k][0]) % mod;
                if(b[j] == b[k] && i > b[j] && dp[i - b[j]][k][0])
                    dp[i][j][1] = (dp[i][j][1] + dp[i - b[j]][k][0]) % mod;
                if(b[j] == a[k] && i > b[j] && a[k] != b[k] && dp[i - b[j]][k][1])
                    dp[i][j][1] = (dp[i][j][1] + dp[i - b[j]][k][1]) % mod;
        }
    }
    ll ans = 0;
    for(int i = 1;i <= n; i++) {
        ans = (ans + dp[L][i][0]) % mod;
        if(a[i] != b[i]) ans = (ans + dp[L][i][1]) % mod;
    }
    cout << ans << endl;
}

signed main() {
    solve();
}

本文作者：jujimeizuo
本文地址： https://blog.jujimeizuo.cn/2021/04/09/codeforces-182e-wooden-fence/
本博客所有文章除特别声明外，均采用 CC BY-SA 3.0 协议。转载请注明出处！