UVALive 8138-Number Generator【概率DP】

妖狐艹你老母 2023-06-12 06:23 11阅读 0赞

题意：随机的给你k个数，范围1~n，问你使得区间\[1, n\]的每个数都出现至少两次的期望次数。

思路：f\[i\]\[j\] 表示有i个数需要出现一次，j个数需要出现两次，那么：

f\[i\]\[j\] = i / n \* f\[i - 1\]\[j\] + j / n \* f\[i + 1\]\[j - 1\] + (n - i - j) / n \* f\[i\]\[j\] + 1

f\[i\]\[j\] = i / (i + j) \* f\[i - 1\]\[j\] + j / (i + j) \* f\[i + 1\]\[j - 1\] + n / (i + j)

这题多样例要记忆化一下否则会超时，但是n不同会导致结果不同，所以把n提出来

#include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int maxn = 3e3 + 10;
    double f[maxn][maxn];
    int vis[maxn];
    int n;
    
    double calc(int i, int j)
    {
        if(i == 0 && j == 0) return 0;
        if(f[i][j]) return f[i][j];
        f[i][j] = 1;
        if(i > 0) f[i][j] += i  * calc(i - 1, j);
        if(j > 0) f[i][j] += j  * calc(i + 1, j - 1);
        f[i][j] = f[i][j] / (i + j);
        return f[i][j];
    }
    
    int main()
    {
        int t;
        scanf("%d", &t);
        while(t--)
        {
            memset(vis, 0, sizeof(vis));
            int k, x;
            scanf("%d%d", &n, &k);
            for(int i = 1; i <= k; ++i) scanf("%d", &x), vis[x]++;
            int cnt1 = 0, cnt2 = 0;
            for(int i = 1; i <= n; ++i)
            {
                if(vis[i] == 1) cnt1++;
                else if(vis[i] == 0) cnt2++;
            }
            printf("%.10f\n", n * calc(cnt1, cnt2));
        }
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，11人围观）

还没有评论，来说两句吧...

相关阅读

相关概率期望dp

简易的入门：http://kicd.blog.163.com/blog/static/126961911200910168335852/ 大神的总结：http://blog

港控/mmm°/ 2023年08月17日 16:25/ 0 赞/ 116 阅读

相关 UVALive 8138-Number Generator【概率DP】

题意：随机的给你k个数，范围1~n，问你使得区间\[1, n\]的每个数都出现至少两次的期望次数。思路：f\[i\]\[j\] 表示有i个数需要出现一次，j个数需要出现两次

妖狐艹你老母/ 2023年06月12日 06:23/ 0 赞/ 11 阅读

相关烟花（概率dp）

https://ac.nowcoder.com/acm/problem/18200 分析： double x = 1.0000 - arr\[i\]; doubl

秒速五厘米/ 2023年01月13日 15:56/ 0 赞/ 220 阅读

相关算法提高概率计算（概率dp）

问题描述　　生成n个∈\[a,b\]的随机整数，输出它们的和为x的概率。输入格式　　一行输入四个整数依次为n，a，b，x，用空格分隔。输出格式　　输出一行包

缺乏、安全感/ 2022年09月28日 15:20/ 0 赞/ 213 阅读

相关 hdu 4586 概率dp

题意：扔一个有n面的骰子，可能得到正面朝上的那个面上面的数字，有一些面比较特殊，扔到这些面上之后可能继续扔，问最终能等到的数字和的期望。分析：这道题

灰太狼/ 2022年08月20日 15:21/ 0 赞/ 187 阅读

相关【dp/二分+暴力】MAGRID UVALive - 5983

Think: 1知识点：dp/二分+暴力 2题意：从(1, 1)点到达(n, m)点，每经过一个点可能会失去能量或者得到能量，询问最小的出发能量使得存在一条路径，路径经

╰半夏微凉°/ 2022年06月09日 14:26/ 0 赞/ 148 阅读

相关 UVALive - 6938 区间dp+离散化

[传送门][Link 1] 思路：一条射线最小的花费就是路径上最高的那个，对于时间这个区间，我们可以将其离散化成1~600的范围，因为有三百个点，最多就600个不同的数，转移

小鱼儿/ 2022年05月17日 12:09/ 0 赞/ 163 阅读

相关 BZOJ3566 概率充电器树形概率dp

[传送门][Link 1] 题意：给你一棵树，求能充电节点的期望个数，每条边都有一个概率，每个点也有一个概率。思路：从反面考虑：设s\[u\]是u没电，以及它的孩

不念不忘少年蓝@/ 2022年05月15日 08:00/ 0 赞/ 232 阅读

相关 UVALive 3983 (单调队列优化dp)

题意：有一个机器人要捡n个垃圾到垃圾桶(0, 0)里，给出了机器人最多可以捡多重的垃圾c，然后给出了n个垃圾的位置和重量，机器人只能按给出的顺序捡垃圾，然后一起扔到垃圾桶里，

青旅半醒/ 2021年12月14日 04:15/ 0 赞/ 292 阅读

相关 UVALive 4015 Caves 洞穴（树形DP）

题意：一棵n个节点的有根树，树的边有正整数权，表示两个节点之间的距离，你的任务是回答这样的询问，从根节点出发，走不超过x单位的距离，最多能走多少个节点，节点经过多次算一个，对

我会带着你远行/ 2021年12月09日 04:21/ 0 赞/ 249 阅读