题解 CF182E 【Wooden Fence】

· · 题解

\text{题目大意}

给定 n 种木板，每种木板有长度和宽度 a_i,b_i。

现在需要从中选一些木板，拼成长度总和为 l 的栅栏，每种木板可以使用无限次。注意你可以将一块木板旋转 90^\circ，使其长度和宽度对调，但这不会改变它的种类。

建出的栅栏要求相邻两块木板：

请你求出有多少种建栅栏的方案数。答案对 10^9+7 取模。

这题可以用 DP 解决。记 f[i][j] 表示当前栅栏长度为 i，最后一块木板种类为 j 的方案数。

对于每一种木板，若其不是正方形，则可以将其拆为长宽分别为 (a,b) 和 (b,a) 的两种木板。但是根据限制条件一，DP 时不能通过这两种木板转移。拆分时需要记录下每种木板原来的种类 c_i。

枚举上一块木板的种类 k，可以得到转移方程：

f[i][j]=\sum f[i-a_j][k] a_j=b_k, c_j\ne c_k 
#include<bits/stdc++.h>
#define p 1000000007
#define nb 210
using namespace std;

int ans, n, l, cnt, a[nb], b[nb], c[nb], f[3010][nb];

// f[i][j] = 当前长度为 i, 最后一块木板为 j 的总方案数
// f[i][j] += f[i - a[j]][k] (a[j] = b[k], c[j] != c[k])

int main(){
    cin >> n >> l;
    for(int i = 1; i <= n; i++){
        c[++cnt] = i;
        cin >> a[cnt] >> b[cnt];
        if(a[cnt] != b[cnt]){
            c[++cnt] = i;
            a[cnt] = b[cnt - 1];
            b[cnt] = a[cnt - 1];
            // 如果不是正方形，将其拆成两种木板
            // 但原来的木板种类仍为 i 
        }
    }
    for(int i = 1; i <= l; i++){
        for(int j = 1; j <= cnt; j++){
            for(int k = 0; k <= cnt; k++){
                if(c[j] == c[k]) continue;      // 若种类相同则跳过 
                if(!k && a[j] == i) f[i][j]++;  // k = 0 代表当前已是第一块木板 
                else if(a[j] == b[k] && i > a[j]){
                    // 根据限制条件二, a[j] = b[k] 
                    f[i][j] = (f[i][j] + f[i - a[j]][k]) % p;
                }
            }
        }
    }
    for(int i = 1; i <= cnt; i++) ans = (ans + f[l][i]) % p;
    cout << ans;
    return 0;
}