Tight Words(数位DP)

缺乏、安全感 2022-08-02 13:48 7阅读 0赞

![20150722143918665][]

#include<cstdio>
    #include<iostream>
    #include<cstring>
    using namespace std;
    double dp[105][12];
    int main()
    {
        int k,n,i,j;
        double gailv,sum;
        while(cin>>k>>n)
        {
            sum=0.0;
            if(n<=1)
            {
                cout<<"100.00000"<<endl;
            }
            else
            {
                memset(dp,0,sizeof(dp));
                gailv=1.0/(k+1);
                for(i=0;i<=k;i++)
                {
                    dp[1][i]=gailv;
                }//第一位的概率！
                for(i=2;i<=n;i++)
                {
                    for(j=0;j<=k;j++)
                    {
                        dp[i][j]+=dp[i-1][j]*gailv;//前面是他本身的概率！
                        if(j>0&&j<=k)//1到k有前面比他小1
                        {
                            dp[i][j]+=gailv*dp[i-1][j-1];//前面比他小1的概率！
                        }
                        if(j>=0&&j<k)//前面比他大1
                        {
                            dp[i][j]+=gailv*dp[i-1][j+1];//前面比他大一的概率！
                        }
                    }
                }
                for(i=0;i<=k;i++)
                {
                    sum+=dp[n][i];
                }
                printf("%.5lf\n",sum*100);
            }
        }
    }

[20150722143918665]: /images/20220731/a8adbb3341f14eda909d0d10ab1597be.png

发表评论取消回复

表情：

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

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

相关阅读

相关数位DP 详解

序 > 天堂在左，战士向右引言数位DP在竞赛中的出现几率极低，但是如果不会数位DP，一旦考到就只能暴力骗分。以下是数位DP详解，涉及到的例题有：

叁歲伎倆/ 2023年08月17日 17:38/ 0 赞/ 140 阅读

相关数位dp小结

数位dp小结关于limit的问题在数位dp中,limit的作用主要有两个。控制枚举的界限，倘若没有界限，每一位的枚举范围都是0-9. 但如果有界限，

桃扇骨/ 2023年07月03日 07:22/ 0 赞/ 20 阅读

相关数位dp总结

数位dp的题目一般问的是某个区间内满足某种性质的数的个数，而且对于数位dp的题目一般有都有比较通用的做法，在考虑问题的时候一般以树的形式来考虑： ![watermark_ty

「爱情、让人受尽委屈。」/ 2022年09月14日 03:06/ 0 赞/ 226 阅读

相关 Bomb（数位Dp）

Bomb Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/65536 K (Java/Oth

布满荆棘的人生/ 2022年08月03日 00:09/ 0 赞/ 202 阅读

相关 Tight Words(数位DP)

![20150722143918665][] include<cstdio> include<iostream> include<cstring>

缺乏、安全感/ 2022年08月02日 13:48/ 0 赞/ 8 阅读

相关数位DP

Problem Description 据说，QAQ 的幸运数字是含有 "47" （4 和 7 相邻）的数，例如 47, 147, 247, 470, 471, 2047

小灰灰/ 2022年06月15日 00:40/ 0 赞/ 309 阅读

相关递推/DP(动态规划)UVA 10081-Tight Words

递推/DP(动态规划)UVA 10081-Tight Words -------------------- 题目链接：[10081 - Tight Wor

矫情吗；*/ 2022年05月16日 09:12/ 0 赞/ 179 阅读

相关 Round Numbers（数位dp）

题目链接： [http://poj.org/problem?id=3252][http_poj.org_problem_id_3252] 分析：本题我一开始思路

墨蓝/ 2022年02月19日 03:39/ 0 赞/ 255 阅读

相关 poj3252（数位dp）

题目链接：https://vjudge.net/problem/POJ-3252 题意：求\[l,r\]之间的Round Number数，RN数即化为二进制后0的个数不少于1

素颜马尾好姑娘i/ 2021年12月21日 01:03/ 0 赞/ 304 阅读

相关数位DP模板

int a[20]; ll dp[20][state]; ll dfs(int pos,/state变量/,bool lead/前导零/,bool li

左手的ㄟ右手/ 2021年09月19日 05:42/ 0 赞/ 371 阅读