CF509F Progress Monitoring(dp)题解

发布于 2020-12-21  196 次阅读


食用前提示:本文搬自作者的洛谷博客。

Tips:由于本人太菜,是看了 @$Skylee$ 大佬的题解才AC的,所以可能内容与他相似,不过加入了一些自己的理解。

如果大佬介意的话我可以重新编排一下,删除相关内容(小声)

题目大意:

找出不同的树 $T$ 的数量,以便以 $T$ 作为输入运行下面给出伪代码的结果恰好是序列 $b$ ,答案对$10 ^9+7$取模。

(两棵树“不同”的定义:它们的邻接矩阵不相同)

数据范围:$ 1\le n \le 500$

used[1 ... n] = {0, ..., 0};

procedure dfs(v):
    print v;
    used[v] = 1;
    for i = 1, 2, ..., n:
        if (a[v][i] == 1 and used[i] == 0):
            dfs(i);

dfs(1);

思路解析:

很明显可以看到这是一个 $DFS$ 序。

不过Skylee大佬说这是一道树形DP,我觉得更像是区间DP。

用 $f[l][r]$ 表示以$b_{l\sim r}$ 为 $DFS$ 序可以对应多少种树的形态。

边界条件:当 $l=r$ 时, $f[l][r]=1$(只有一个结点)

转移方程为$f[l][r]=\sum_{l<k\le r,b_{k+1}<b_{l+1}}f[l+1][k]\times f[k][r]$

诶,没错,就是和 $Skylee$ 大佬写的一样,但是我这里加入了一些自己的理解:

(注意,对于这里的 $f[l][r]$ ,我们认为它是以 $l$ 为根的对于当前区间,我们枚举第一个子树到哪里为止。转移方程中乘以 $f[k][r]$ 的含义是以 $k$ 为根的另一个树作为答案,把 $k$ 去掉后合并到以 $l+1$ 为根的子树里。因为 $k+1$ 一定是 $k$ 的第一个儿子,$f[k][r]$ 的所有除了 $k+1$ 的儿子全都大于 $a[k+1]$ ,所以只需要判断 $a[l+1]<a[k+1]$ 。)

代码1(看完别走开):

#include<bits/stdc++.h>
using namespace std;
const int Mod=1000000007;
const int N=505;

int n,a[N];
long long f[N][N];

inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while (!isdigit(ch)) { if (ch=='-') f=-1; ch=getchar(); }
    while (isdigit(ch)){ x=x*10+ch-'0'; ch=getchar(); }
    return x*f;
}

inline long long dfs(int l,int r){
    if (l==r) return 1;
    if (f[l][r]) return f[l][r];
    for (int k=l+1;k<=r;k++){
        if (k!=r&&a[k+1]<a[l+1]) continue;
        f[l][r]=(f[l][r]+dfs(l+1,k)*dfs(k,r))%Mod;
    }
    return f[l][r];
}

int main(){
    //freopen("CF509F.in","r",stdin);
    //freopen("CF509F.out","w",stdout);
    n=read();
    for (int i=1;i<=n;i++)
        a[i]=read();
    memset(f,0,sizeof(f));
    printf("%lld\n",dfs(1,n));
    return 0;
}

不过你以为就这么结束了?

都说记忆化搜索是DP的一种实现方式,那么我们自然可以把它改成DP。

很好想,三层循环,第一层枚举区间长度,第二层枚举区间左端点,第三层枚举区间分割点(也就是根),转移方程同上。

从这里我们就可以看出时间复杂度显然是 $O(n^3)$了。

代码2:

#include<bits/stdc++.h>
using namespace std;
const int Mod=1000000007;
const int N=505;

int n,a[N];
long long f[N][N];

inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while (!isdigit(ch)) { if (ch=='-') f=-1; ch=getchar(); }
    while (isdigit(ch)){ x=x*10+ch-'0'; ch=getchar(); }
    return x*f;
}

int main(){
    //freopen("CF509F.in","r",stdin);
    //freopen("CF509F.out","w",stdout);
    n=read();
    for (int i=1;i<=n;i++)
        a[i]=read();
    memset(f,0,sizeof(f));
    for (int i=1;i<=n;i++) f[i][i]=1;
    for (int len=2;len<=n;len++)        //枚举长度 
        for (int l=1;l<=n-len+1;l++){       //枚举起点 
            int r=l+len-1;
            for (int k=l+1;k<=r;k++){       //枚举分割点 
                if (k!=r&&a[k+1]<a[l+1]) continue;
                f[l][r]=(f[l][r]+f[l+1][k]*f[k][r])%Mod;
            }
        }
    printf("%lld\n",f[1][n]);
    return 0;
}

都看到这里了不点个赞么(小声)


我们无法选择过去,但我们可以改变未来。