The Debut Album

題目鏈接：

http://acm.hust.edu.cn/vjudge/contest/126546#problem/G

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 ? remixes. On second thoughts the
musicians decided that the album will be of interest only if there are no more than ? remixes on “My
love” in a row and no more than ? 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 ? 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 ? in one variant at ?-th place stands one and in another
variant at the same place stands two.

Input

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

Output

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

Examples

3 2 1
4

Explanation

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

題意：

英語弱雞表示題意真難看懂.
在n個位置填充1 or 2. 要求連續的1的個數不超過a，連續的2的個數不超過b.
求方案數.

題解：

要考慮每一位可能放1或2，容易想到動態規劃：
dp[i][1/2][j]：到第i個位置時，放1且有連續j個1的方案(放2且有連續j個2的方案).
轉移方程：
j==1: dp[i][1][1] = Σdp[i-1][2][k] ,(k<=b), 即只放一個1的情況等同于前面有任意個連續2的情況.
dp[i][2][1] = Σdp[i-1][1][k] ,(k<=a), 即只放一個2的情況等同于前面有任意個連續1的情況.
j!=1: dp[i][1/2][j] = dp[i-1][1/2][j-1];


上述思路確定后，考慮數組內存的問題，由于n比較大，直接開三維數組估計會MLE.
由于轉移具有線性型(i只能由i-1來). 所以可以用滾動數組壓縮到二維數組.
注意考慮壓縮后的各種問題：
如果后面需要的值在前面被改變了，那么就先需要記錄下來.
對j進行枚舉時，由于j用到j-1的值，所以要從大往小枚舉.


一個簡單的滾動數組dp寫了一個小時，一直在瞎處理邊界.
歸根結底還是太弱了，dp還需多加練習.

代碼：

#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <queue> #include <map> #include <set> #include <vector> #define LL long long #define eps 1e-8 #define maxn 550 #define mod 1000000007 #define inf 0x3f3f3f3f #define IN freopen("in.txt","r",stdin); using namespace std;int n, a, b; int dp[2][350];int main(int argc, char const *argv[]) {//IN;while(scanf("%d %d %d", &n,&a,&b) != EOF){memset(dp, 0, sizeof(dp));dp[0][1] = dp[1][1] = 1;for(int i=2; i<=n; i++) {/*由于要滾動處理，先記錄下會改變的值*/int tmpa = dp[0][1];int tmpb = dp[1][1];dp[0][1] = 0;for(int j=1; j<=b; j++)dp[0][1] = (dp[0][1] + dp[1][j]) % mod;dp[1][1] = tmpa;for(int j=2; j<=a; j++)dp[1][1] = (dp[1][1] + dp[0][j]) % mod;/*由于要滾動處理，需要從后往前覆蓋*/for(int j=a; j>=3; j--) {dp[0][j] = dp[0][j-1];}if(a >= 2) dp[0][2] = tmpa;for(int j=b; j>=3; j--) {dp[1][j] = dp[1][j-1];}if(b >= 2) dp[1][2] = tmpb;}int ans = 0;for(int i=1; i<=a; i++)ans = (ans + dp[0][i]) % mod;for(int i=1; i<=b; i++)ans = (ans + dp[1][i]) % mod;printf("%d\n", ans);}return 0; }

轉載于:https://www.cnblogs.com/Sunshine-tcf/p/5746635.html

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的Gym 100507GThe Debut Album （滚动数组dp）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。