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

其实这是一道好题。首先考虑数据范围提示您

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。

CPP

#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;
}

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

文章操作

相关推荐

评论

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