URAL 2018. The Debut Album （dp）

URAL 2018. The Debut Album （dp）

Description

Pop-group “Pink elephant” entered on recording their debut album. In fact they have only two songs: “My love” and “I miss you”, but each of them has a large number of remixes.The producer of the group said that the album should consist of n remixes. On second thoughts the musicians decided that the album will be of interest only if there are no more than a remixes on “My love” in a row and no more than b remixes on “I miss you” in a row. Otherwise, there is a risk that even the most devoted fans won’t listen to the disk up to the end.How many different variants to record the album of interest from n remixes exist? A variant is a sequence of integers 1 and 2, where ones denote remixes on “My love” and twos denote remixes on “I miss you”. Two variants are considered different if for some i in one variant at i-th place stands one and in another variant at the same place stands two.

Input

The only line contains integers n, a, b (1 ≤ a, b ≤ 300; max(a,b) + 1 ≤ n ≤ 50 000).

Output

Output the number of different record variants modulo 109+7.

Sample input

3 2 1

Sample output

4

题意

一个长度为 ​​n​​​ 的数列，其中 ​​1​​​ 连续的个数不能超过 ​​a​​​ ， ​​2​​​ 连续的个数不能超过 ​​b​​ ，问总共有多少个这样的数列。

思路

​​dp[i][k]​​​ 代表长度为 ​​i​​​ 的数列，以 ​​k​​ 结尾并满足题意的个数。

则有： ​​dp[i][k]+=dp[i-j][k^1]​​

其中 ​​dp[i-j][k^1]​​​ 代表当前点 ​​i​​​ 之前最远距离为 ​​a||b​​ 的那一点与当前点不同的情况，因为在这个范围以内都满足题意。

AC 代码

#includeusing namespace std;const int mod=1e9+7;int dp[51000][2];int main(){ int n,a,b; cin>>n>>a>>b; dp[0][0]=dp[0][1]=1; for(int i=1; i<=n; i++) { for(int j=1; j<=min(i,a); j++) dp[i][0]=(dp[i][0]+dp[i-j][1])%mod; for(int j=1; j<=min(i,b); j++) dp[i][1]=(dp[i][1]+dp[i-j][0])%mod; } cout<<(dp[n][0]+dp[n][1])%mod; return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。