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

矫情吗；* 2022-05-16 09:12 178阅读 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 条评论，178人围观）

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

相关阅读

相关 hdu5286 dp+递推

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

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

相关 hdu5375 dp+递推

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

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

相关 hdu4489 dp+递推

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

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

相关 uva 437 动态规划

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

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

相关 uva 10003 动态规划

给定一个长度为len的木板，要在n个位置处切开，每次切开的代价是这块木板的长度，求最小的代价。其实切木板跟合并木板是等价的。。开始以为是简单的贪心，便写了一个优先

待我称王封你为后i/ 2022年08月03日 13:41/ 0 赞/ 14 阅读

相关 uva 11584 动态规划

给定一串字符串，看最少能把它分成几个回文字符串。 SampleInput 3 racecar fastcar aaadbccb SampleOutput 1 7

向右看齐/ 2022年08月03日 13:41/ 0 赞/ 12 阅读

相关 Tight Words(数位DP)

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

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

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

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

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

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

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

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

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

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

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