【1】P10741 [SEERC 2020] Fence Job【动态规划】

ExFish · 2025-11-24 15:32:23 · 题解

其实这是一道好题。首先考虑数据范围提示您 n^2 轻松拿捏。然后我们考虑如何设计状态。f_{i,j} 为操作前 i 个数，已经完成了 j 的部署的不同方案数。显然答案为 f_{n,n}。我们考虑如何转移。你发现有这样的转移：f_{i,j}\leftarrow f_{i-1,j}。也就是考虑一个不操作。还有这样的转移：f_{i,j}\leftarrow f_{i,j-1}，表示可以使用操作扔掉 j。这种转移的限制为可以拓展的区间，要不然最小值就不是 h_i 了，也就无法通过操作转移。

类似题目：AGC058B。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=3e3+10;
const ll P=1e9+7;
int n;
ll f[N][N],h[N];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>h[i], f[i][0]=1;
    for(int i=1;i<=n;i++){
        int l=i,r=i;
        for(;h[l-1]>h[i];--l);
        for(;h[r+1]>h[i];++r);
        for(int j=1;j<=n;j++){
            if(l<=j&&j<=r)
                f[i][j]=(f[i-1][j]+f[i][j-1])%P;
            else
                f[i][j]=f[i-1][j];
        }
    }
    cout<<f[n][n];
    return 0;
}