URAL 2018 The Debut Album

题意呐就是给一个n位的二进制数, 要求:
连续的0不能超过a个.
连续的1不能超过b个.
问这种二进制数共多少种?
1<=n<=50000
1<=a, b<=300

分析
..:
就是这样简单的DP我等渣新也是想了许久..
稿纸上写写画画后总结出第一种转移:

 d[x][k][w] - 在x位置时已有连续k个w时的种数

那么

d[x][k][w]=d[x+1][1][1-w]

d[x][k][w]+=d[x+1][k+1][w], if k<a when w is 0, or k<b when w is 1

时间复杂度应该是O(nab)?..

但是..空间严重超出64MB..

于是继续埋头观察稿纸, 研究规律..良久..咦!..

出现了:

d[x][w] - 当前位置x是w时的种数

那么

d[x][w]=d[x][w]+d[x+k][1-w], for k from 1 to a when w is 0, or from 1 to b when w is 1
时间复杂度同上(应该..)

写出代码

..:

#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007

int d[50001][2];
int ab[2];
int n;
inline int dodp(int x, int w) {
  if (x==n) {
    return 1;
  } else {
    int& r=d[x][w];
    if (r==-1) {
      r=0;
      for (int i=1; i<=ab[w]; i++) if (x+i<=n) {
        r=(r+dodp(x+i, 1-w))%mod;
      }
    }
    return r;
  }
}
int main(void) {
  scanf("%d%d%d", &n, &ab[0], &ab[1]);
  memset(d, 0xff, sizeof d);
  printf("%d\n", (dodp(0, 0)+
    dodp(0, 1))%mod);
}