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

矫情吗；* 2022-05-16 09:12 151阅读 0赞

*  # 递推/DP(动态规划)UVA 10081-Tight Words #

--------------------

*  ## 题目链接：[10081 - Tight Words][] ##
 *  ## 思路： ##

**题目大意是有一个序列长度为n，是由0~k组成的，问得到序列相邻数字差距不大于1的概率是多少**

![70][]

假设***目前已经排好了 前 i-1个数字，目前要排第i个数字，并且第i个数字是 j***，那么**第i个数字与相邻（也就是第i-1个数字）差距不大于的情况只有当i-1个数字为**：**j >=0 下的j-1，j，j+1**，把长度i-1序列可能情况概率加起来乘上 1/(k+1)---**因为第i个数字为j的概率为 1/(k+1)**

**DP初态是i=1时，这个时候数字为j（j>=0,j<=k）的概率为 1/(k+1)**

*  ## 代码： ##

#include<iostream>
    #include<iomanip>
    #include<cmath>
    using namespace std;
    
    int main()
    {
        int k,n;
        while(cin>>k>>n)
        {
            double DP[105][10]={0};
            double Res=0.0;
            for(int i=0;i<=k;i++)
                DP[1][i]=1.0/(k+1);
            for(int i=2;i<=n;i++)
            {
                for(int j=0;j<=k;j++)
                {
                    for(int l=0;l<=k;l++)
                        if(abs(l-j)<=1)   //ok
                        {
                            DP[i][j]+=DP[i-1][l]*(1.0/(k+1));
                            //cout<<DP[i][j]<<endl;
                        }
                }
            }
            for(int i=0;i<=k;i++)
                Res+=DP[n][i];
            cout<<fixed<<setprecision(5)<<Res*100<<endl;
        }
        return 0;
    }

[10081 - Tight Words]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1022
[70]: /images/20220516/c9a187ede3734276a7886e63ea7b18d8.png

发表评论取消回复

表情：

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

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

相关阅读

相关动态规划-树形DP

文章目录树形DP HDU-1520 HDU-2196 树形DP -------------------- 树形DP，顾名思义是在「树」这种数

淩亂°似流年/ 2023年03月04日 06:40/ 0 赞/ 170 阅读

相关 576 出界的路径数（动态规划-递推）

1. 问题描述：给你一个大小为 m x n 的网格和一个球。球的起始坐标为 \[startRow, startColumn\] 。你可以将球移到在四个方向上相邻的单元格内（

左手的ㄟ右手/ 2022年08月31日 11:10/ 0 赞/ 133 阅读

相关 hdu5286 dp+递推

题意：有n个人，每个人有一个value值，有两扇门A,B分别各有一个value，现在要讲n个人分为两组分别从两个门进入，要求是每组人的value值的和（迭代的求，直至变为一

本是古典何须时尚/ 2022年08月19日 14:28/ 0 赞/ 120 阅读

相关 hdu5375 dp+递推

题意：给出一段二进制码，其中有些位置的数字不确定用"?"表示，这些位置可以为0也可以为1，然后将这个数字的所有可能转化为相应的格雷码，格雷码对应的数字串中位置为i的数字是1

╰半夏微凉°/ 2022年08月19日 14:23/ 0 赞/ 126 阅读

相关 hdu4489 dp+递推

题意：有n个高矮不同的士兵，现在要将他们按高，矮依次排列，问有多少种情况。分析：组合dp问题。假设n个士兵的身高分别为1，2......n。我们现在考虑n个

待我称王封你为后i/ 2022年08月19日 14:21/ 0 赞/ 135 阅读

相关 uva 437 动态规划

给定一些立方体，每种立方体有长宽高三个属性，可以任意变换摆放姿势，每种立方体有无限个，要把其中的一些摆起来，求最大的高度。要求在上面的立方体必须底部的长宽都小于在下面的立方体的

青旅半醒/ 2022年08月03日 13:42/ 0 赞/ 135 阅读

相关算法笔记动态规划递推写法

1. 什么是动态规划动态规划是一种用来解决一类最优化问题的算法思想。简单来说，动态规划将一个复杂的问题分解成若干个子问题，通过综合子问题的最优解来得到原问

蔚落/ 2022年06月01日 08:28/ 0 赞/ 195 阅读

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

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

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

相关贪心/DP(动态规划)-UVA 10440-Ferry Loading II

贪心/DP(动态规划)-UVA 10440-Ferry Loading II -------------------- 题目链接：[10440 - Ferry

「爱情、让人受尽委屈。」/ 2022年05月15日 22:14/ 0 赞/ 156 阅读

相关算法——动态规划(DP）

动态规划问题，大致可以通过以下四部分进行解决：划分阶段：按照问题的时间或空间特征，把问题分为若干个子阶段。（划分后的子阶段一定要是有序的或者是可排序的，否则问题就无法

谁践踏了优雅/ 2021年10月18日 09:48/ 0 赞/ 390 阅读