[SEERC 2020] Fence Job

题目描述

有n根长度为1的木板，需要排列成一个栅栏。栅栏由若干列组成，每列的木板数为正整数，且所有列的木板数之和为n。栅栏的形状需满足相邻两列的木板数之差不超过1（即|h_i - h_{i+1}| ≤ 1）。求满足条件的栅栏形状的数量。

解题思路

使用线性动态规划（DP）解决。定义状态dp[i][j]表示用i根木板搭建栅栏，最后一列高度为j的方案数。通过状态转移方程计算所有可能的方案数，最终求和得到结果。

状态定义与转移

• 状态定义：dp[i][j] = 用i根木板搭建栅栏，最后一列高度为j的方案数。
• 状态转移：由于相邻列高度差不超过1，前一列高度可为j-1、j或j+1，因此： [ dp[i][j] = dp[i-1][j-1] + dp[i-1][j] + dp[i-1][j+1] ] 边界条件：若j=1，则j-1=0不合法，仅考虑j和j+1；若j较大，j+1可能超出范围，需限制。

代码实现

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9 +7;
const int MAXN = 2005;

int dp[MAXN][MAXN]; // dp[i][j]表示i根木板，最后高度j的方案数

int main() {
    int n; cin >> n;
    // 初始化：1根木板时，只有1种方案（高度1）
    dp[1][1] = 1;
    for (int i = 2; i <= n; ++i) { // 枚举木板总数i
        for (int j = 1; j <= i; ++j) { // 枚举最后一列高度j <= i
            // 前一列高度可能为j-1, j, j+1
            if (j-1 >= 1) dp[i][j] = (dp[i][j] + dp[i-1][j-1]) % MOD;
            dp[i][j] = (dp[i][j] + dp[i-1][j]) % MOD;
            if (j+1 <= i-1) dp[i][j] = (dp[i][j] + dp[i-1][j+1]) % MOD;
        }
    }
    // 求和所有可能的最后高度
    int ans = 0;
    for (int j = 1; j <= n; ++j) {
        ans = (ans + dp[n][j]) % MOD;
    }
    cout << ans << endl;
    return 0;
}

E98 线性DP P10741 [SEERC 2020] Fence Job

// 线性DP O(n^2)
#include <bits/stdc++.h>
using namespace std;

const int N=3005,M=1e9+7;
int n,a[N],f[N][N];

signed main(){
  scanf("%d",&n);
  for(int i=1;i<=n;i++) scanf("%d",&a[i]);
  for(int i=1;i<=n;i++) f[i][0]=1;
  for(int i=1,l,r;i<=n;i++){
    for(l=i;a[l-1]>a[i];l--);
    for(r=i;a[r+1]>a[i];r++);
    for(int j=1;j<=n;j++){
      f[i][j]=f[i-1][j]+f[i][j-1]*(l<=j&&j<=r);
      f[i][j]%=M;
    }
  }
  cout<<f[n][n];
}