渣新:..: October 2014

这个题直接看了Nocow上的代码..
很简单的DP解法..因为之前也遇到过类似的题目没有A掉, 抄完代码也没深入去想就不了了之..
这样是不对的..于是在这题的DP解法上好好想了想..

分析
..:
先说状态转移:

d[x][w] - x位置的数被分为单增(w=1)或分为单减(w=0)时的最小段数
d[x][w]=d[x-1][w], if no turning
=min(d[x-1][0]+d[x-1][1])+1, if a turning encountered

伪代码
..:
d[a][0]=1;
d[b][1]=1;
for i from a to b:
if F[i]>F[i-1]:
d[i][0]=min(d[i-1][0], d[i-1][1])+1;
else
d[i][0]=d[i-1][0]
if F[i]<F[i-1]:
d[i][1]=min(d[i-1][0], d[i-1][1])+2;
else
d[i][1]=d[i-1][1]

答案就是min(d[b][0], d[b][1])

什么乱起八糟的呐这是..
对区间上的每一个拐点, 我们可以把他归为之前的结尾, 或之后的起点, 也就是说..
1 2 3 4 5 4 3
F[i]=4<F[i-1]=5, 拐点来了..那么i-1既可以是起点, 又可以是终点, 如下:
1 2 3 4 | 5 4 3
1 2 3 4 5 | 4 3

完了..

题意呐就是给一个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);
}

URAL 1346 Intervals of Monotonicity

URAL 2018 The Debut Album