URAL 2018 The Debut AlbumDP中滚动数组用法

题目描述：

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 10 9+7. Sample Input input

3 2 1

output

4

Notes

In the example there are the following record variants: 112, 121, 211, 212.

题目分析：

n个位置，有两种物品，其中第一个物品不能连续超过a个，第二个物品不能连续超过b个。 很明显的DP题。任何人都能想到dp[i][j][k]来存状态，其中在i位置，选择j种物品，其中有k个连续的该物品。 但是，我们看n的范围是[1,50000]，a和b的范围是[1,300]。所以这个dp数组是50000*2*300的范围，肯定是MLE的。 这个时候就需要用到滚动数组了。 因为我们可以知道，这个dp状态转移方程中，下一状态只与其上一个状态有关，那么我们其实可以将i位置范围改成2，变成一个dp[2][2][300]的dp数组，这样就不会爆内存了。而关于这个滚动数组的用法，具体思想可以参考http://blog.csdn.net/niushuai666/article/details/6677982。 如果不看滚动数组，dp的转移方程也很容易推导的。我就不多赘述了。

代码如下：

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef long long LL; const int MOD=1e9+7; int n,a,b; LL dp[2][2][310]; int ans; int main() { while(scanf("%d%d%d",&n,&a,&b)!=-1) { memset(dp,0,sizeof(dp)); dp[0][0][0]=1; dp[0][1][0]=1; ans=0; for(int i=1; i<=n; i++) { int now=i&1; int pre=now^1; // if (now==1 && pre==0) // printf("%d %d\n",pre+i-1,now+i-1); // else if (now==0 && pre==1) // printf("%d %d\n",pre+i-2,now+i);//原数组位置 memset(dp[now],0,sizeof(dp[now])); for(int j=1; j<=a; j++) { dp[now][0][j]+=dp[pre][0][j-1]; dp[now][0][j]%=MOD; dp[now][1][1]+=dp[pre][0][j]; dp[now][1][1]%=MOD; } for(int j=1; j<=b; j++) { dp[now][1][j]+=dp[pre][1][j-1]; dp[now][1][j]%=MOD; dp[now][0][1]+=dp[pre][1][j]; dp[now][0][1]%=MOD; } } for(int i=1; i<=a; i++) { ans+=dp[n&1][0][i]; //printf("%I64d\n",dp[n&1][0][i]); ans%=MOD; } for(int i=1; i<=b; i++) { ans+=dp[n&1][1][i]; //printf("%I64d\n",dp[n&1][1][i]); ans%=MOD; } printf("%d\n",ans); } return 0; }