首页 > 其他分享 >动态规划--放置油桶

动态规划--放置油桶

时间:2024-01-20 16:38:27浏览次数:26  
标签:空位 -- 位置 放桶 int 放置 dp 油桶

题目:


题目:

#include<iostream>
#include<cstdio>
using namespace std;
int n,k,dp[1000005];
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=k+1;i++)
        dp[i]=i+1;//dp[i]表示当n=i时的答案
    for(int i=k+2;i<=n;i++)
        dp[i]=(dp[i-k-1]+dp[i-1])%1000000007;//dp[i-k-1]表示在第i个位置放一个桶,dp[i-1]表示第i个位置不放
    printf("%d",dp[n]);
    return 0;
}

方法总结:

动态规划

首先开一个数组,dp[i]表示以i个空位的策划方案数

初始化:

i<=k+1就是当空位数小于等于最小相隔数加一,也就是第一个位置向右小于等于k,那么最多放一个桶(0个桶或一个桶)-->所以这种情况策划方案数为i+1,即不放桶(1种),放一个桶(i个空位任意一个空位放桶即i种)

当k+1<i<=n:

写动态规划式子

那么dp[i]策划方案数为

dp[i]=dp[i-k-1]+dp[i-1]

包括:两项

(1)第i个位置放桶

就是第i个位置放桶则上一个桶位置最右为i-k-1     -->相隔k个位置,向左k+1个 位置

(2)第i个位置不放桶

第i个位置不放就和i-1个位置相同

两种情况相加

dp[i]=dp[i-k-1]+dp[i-1]

最后输出dp[n]表示输入的n个空位方案数

 

标签:空位,--,位置,放桶,int,放置,dp,油桶
From: https://www.cnblogs.com/luckyyaoyao/p/17976671

相关文章

  • KMP
    KMPvoidgetnext(char*p){intlenp=strlen(p);nextt[0]=-1;intk=-1;intj=0;while(j<lenp-1){//p[k]表示前缀,p[j]表示后缀(并没有“真”!)if(k==-1||p[j]==p[k])//j在这{j++;//j+1在这k++;//k=k+1//---->若......
  • Miller Rabin素数判定
    MillerRabin素数判定llqmul(lla,llb,llmod)//快速乘{llc=(ld)a/mod*b;llres=(ull)a*b-(ull)c*mod;return(res+mod)%mod;}llqpow(lla,lln,llmod)//快速幂{llres=1;while(n){if(n&1)res=qmul(res,a,mod);......
  • 欧拉筛
    欧拉筛boolisprime[MAXN];//isprime[i]表示i是不是素数intprime[MAXN];//现在已经筛出的素数列表intn;//上限,即筛出<=n的素数intcnt;//已经筛出的素数个数voideuler(){memset(isprime,true,sizeof(isprime));//先全部标记为素数ispri......
  • 大数因数分解Pollard_rho
    大数因数分解Pollard_rho#include<iostream>#include<cstdio>#include<algorithm>#include<cmath>#include<cstring>#include<map>usingnamespacestd;constinttimes=50;intnumber=0;map<long......
  • 马拉车算法
    马拉车算法chars[maxn],ss[maxn];intp[maxn];intlen,center;intcnt=1;voidinit(){memset(s,0,sizeofs);cnt=1,s[0]='@';intlen=strlen(ss);for(inti=0;i<len;i++){s[cnt++]='#';s[cnt++]=ss......
  • HTML基础
    HTML标准结构标签的语义Meta元信息META标签,是在HTML网页源代码中一个重要的html标签。META标签用来描述一个HTML网页文档的属性,例如作者、日期和时间、网页描述、关键词、页面刷新等。META标签元素可提供有关页面的元信息(meta-information),比如针对搜索引擎和更新频......
  • 我与计算机
    当我第一次接触到计算机,我就被它的神秘和无穷魅力深深吸引。那时的我,还是一个对科技一无所知的小男孩,但当我坐在电脑前,敲打着键盘,看着屏幕上的光标闪烁时,我仿佛打开了通往新世界的大门。从那时起,我就对计算机充满了浓厚的兴趣和好奇心,开始探索这个充满无限可能的领域。大学时,我毅......
  • 盒子模型
    盒子模型块级元素display:block独占一行,对宽度、高度、对齐方式等支持例如:divullih1-h6p等内联级元素display:inline不独占一行,对宽度、高度、对齐方式等不支持,跟(块级相反)例如:aspan等内联块级元素display:inline-block不独占一行,对宽度、高......
  • 深度学习-神经网络原理-39
    目录1.神经网络算法是有监督的学习算法,2.分类3.训练4.代码进入新的内容,深度学习啦万事万物的产生不是一下子就变出来的,学术上也是,一点点的进步才催生出一门新的学科或者技术,神经网络用于机器学习也不例外,前面的机器学习的内容,线性回归,逻辑回归,多分类,决策树,以及各种集成学习......
  • 程序是怎么跑起来的第一章阅读
    读了这本书的第一张,让我对电脑cpu结构的更加有所了解,刚开始只知道cpu是电脑运行效果的影响和温度的显示,后来才知道原来cpu对电脑这么的重要,一个电脑的好坏也取决于它cpu的性能如何,它的内部由寄存器,控制器,运算器和时钟四个部分构成,由程序员输入的命令在电脑后台变成程序编码,然后寄......