LP3830 [SHOI2012] 随机树 [期望/DP]

Author Avatar
空気浮遊 2018年09月21日
  • 在其它设备中阅读本文章
  • dp
  • 树状dp
  • 期望
  • 分享到 Facebook
  • 分享到 Telegram
  • 分享到 Twitter
  • 分享到微博

Problem

https://www.luogu.org/problemnew/show/P3830

Solution

联动:https://pst.iorinn.moe/archives/sol-usaco-nocows.html

第一问求可能的深度期望总和。

$f_{i,j}$ 现深度为 i,剩 j 次展开的深度期望和。方程略。

第二问求最深深度期望。

$f_{i,j}$ 深度一定为 i,剩 j 次展开的树的概率。
$S_{i,j}$ 深度 $\leq i$,剩 j 次展开的树的概率。

左右子树分配展开数一共有 $j$ 种可能,由乘法和加法原理有:
$$f_{i,j} =\frac{1}{j} \sum_{x=0}^{j-1} f_{i-1, j-1-x}*(2S_{i-2,x}+f_{i-1, x})$$

$S$ 就是前缀和。

$f_{0,0}=1$。


考虑一次转移,我们令左子树 $k$ 次展开,右子树 $j-k$ 次展开。考虑这样子情况下的分配合法概率。

分配展开的概率相同,为 $\frac {1}{j}$,因此根据全概率公式有如上的 dp 方程。

Code

// Code by ajcxsu
// Problem: random_tree

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

typedef long long ll;
const int N=110;
int q, n;

namespace solve1 {
    double f[N][N];
    char vis[N][N];
    double dfs(int i, int j) {
        if(j==0) return i;
        if(vis[i][j]) return f[i][j];
        vis[i][j]=1;
        for(int k=0;k<=j-1;k++) f[i][j]+=dfs(i+1, k)+dfs(i+1, j-1-k);
        return f[i][j]/=j;
    }
    void work() {
        cout<<dfs(0, n-1)/n<<endl;
    }
}

namespace solve2 {
    double f[N][N], f3[N][N];
    char vis[N][N], vis2[N][N];
    double dp(int, int);
    double S(int, int);
    double dp(int x, int y) {
        if(x==0) return y==0;
        if(y<x) return 0;
        if(vis[x][y]) return f[x][y];
        f[x][y]=0, vis[x][y]=1;
        for(int i=0;i<=y-1;i++)
            f[x][y]=f[x][y]+dp(x-1, y-i-1)*(S(x-2, i)*2+dp(x-1, i));
        return f[x][y]/=y;
    }
    double S(int x, int y) {
        if(x<0) return 0;
        if(vis2[x][y]) return f3[x][y];
        f3[x][y]=0, vis2[x][y]=1;
        for(int i=0;i<=x;i++) f3[x][y]+=dp(i, y);
        return f3[x][y];
    }
    double cnt[N], tot;
    void work() {
        double ans=0;
        for(int i=1;i<=n-1;i++)
            ans+=1.0*i*(cnt[i]=dp(i, n-1));
        cout<<ans<<endl;
        return;
    }
}

int main() {
    cout.setf(ios::fixed), cout<<setprecision(6);
    cin>>q>>n;
    if(q==1) solve1::work();
    else solve2::work();
    return 0;
}

本文链接:https://pst.iorinn.moe/archives/sol-luogu-3830.html
许可: https://pst.iorinn.moe/license.html
若无特别说明,博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆

      新篇
旧篇      
    • fingerprint Login
  • home 主页
  • inbox 归档
    • December 2024 1
    • August 2024 1
    • June 2024 1
    • April 2024 3
    • March 2024 1
    • February 2024 2
    • January 2024 1
    • November 2023 1
    • August 2023 1
    • May 2023 1
    • February 2023 2
    • January 2023 2
    • July 2022 1
    • June 2022 1
    • April 2022 1
    • March 2022 1
    • February 2022 2
    • December 2021 1
    • November 2021 1
    • August 2021 3
    • July 2021 3
    • April 2021 2
    • March 2021 1
    • February 2021 4
    • January 2021 2
    • December 2020 1
    • November 2020 1
    • October 2020 3
    • September 2020 1
    • August 2020 1
    • July 2020 1
    • March 2020 1
    • December 2019 1
    • September 2019 1
    • July 2019 1
    • April 2019 2
    • March 2019 13
    • February 2019 15
    • January 2019 11
    • December 2018 3
    • November 2018 6
    • October 2018 28
    • September 2018 32
    • August 2018 19
    • July 2018 13
    • June 2018 27
    • May 2018 11
    • April 2018 12
    • March 2018 19
    • February 2018 8
    • January 2018 7
    • December 2017 2
    • November 2017 2
  • apps 分类
    • 笔记
    • 题解
    • 杂文
    • 技术
    • 游戏
    • 小说
  • 留言板
  • 关于
  • 友链
  • 文章总数 282
主题 - Material i
expand_less
Copyright © 2025 雪屋
Float in air.
Powered by Typecho
Theme - Material