题目:
题目:
#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