【Week3 周报】递推专题

· · 个人记录

一、 P1192 台阶问题

  1. 问题：有 N 级台阶，你一开始在底部，每次可以向上迈 1∼K 级台阶，问到达第N 级台阶有多少种不同方式。

  2. 分析：设f [ i ]表示走到第i级台阶的方案数。利用以下递推式的时间复杂度 O（n），正常来做需要 O（n^k）

  3. 注意边界问题：上式只有在n>=k+1时才成立，n<=k时 f [ n ] = 2 f [ n - 1 ]，并且 f [ 0 ] = f [ 1 ] = 1

  4. 注意取模出现负数现象： 所以最后的答案 ans = (ans + mod) % mod最为保险

  5. 代码：

      #include <cstdio>
  const int N=1e5+10;
  const int m=100003;
  using namespace std;
  int n,k,f[N]; 
  int main(){
      scanf ("%d%d",&n,&k);
      f[0]=f[1]=1;
      for (int i=2;i<=k;i++)
          f[i]=(2*(f[i-1]%m))%m;
      for (int i=k+1;i<=n;i++)
          f[i]=(((2*f[i-1])%m)-(f[i-k-1]%m))%m;
      printf ("%d\n",(f[n]+m)%m);
      return 0;
  }

二、 P1028 [NOIP2001 普及组] 数的计算

  1. 问题：给出正整数 n，要求按如下方式构造数列：只有一个数字 n 的数列是一个合法的数列； 在一个合法的数列的末尾加入一个正整数，但是这个正整数不能超过该数列最后一项的一半，可以得到一个新的合法数列。求一共有多少个合法的数列，两个合法数列 a,b 不同当且仅当两数列长度不同或存在一个正整数 i≤∣a∣，使得ai不等于bi。 例如n=6时有（6）（6，1）（6，2）（6，3）（6，2，1）（6，3，1）六组

  2. 分析：由于该题解法多样，我们选择最易理解的递推做法进行阐释。 设 f [ n ] 表示给出数字是n的时候符合条件的方案数。那么，这题从奇偶角度进行分析。

  3. 步骤：对于 f [ 2n ]，我们考虑 f [ 2n - 1 ]，f [ 2n - 1 ] 中必然涵盖了 f [ 2n ] 中的大部分解，但也存在少部分未涵盖到。这是因为 f [ 2n - 1 ] 是由 f [ 1 ] 到 f [ n - 1 ] 求和得来的，(2n - 1) / 2下取整的结果是n - 1，那么 f [ n ] 就是那个未被涵盖到的解。 对于 f [ 2n + 1 ]，我们考虑 f [ 2n ]。f [ 2n ]中涵盖到了f [ 2n + 1 ] 的所有解。这是因为 f [ 2n ] 是由 f [ 1 ] 到 f [ n ] 求和得来的，而 (2n + 1) / 2 下取整的结果恰为 n。 综上，我们得到以下递推式：

  4. 边界问题： f [ 1 ] = 1

  5. 代码：

    #include <cstdio>
const int N=1010;
using namespace std;
int n, f[N]={0,1};
int main(){
    scanf ("%d",&n);
    for (int i=2;i<=n;i++)
        if (i&1) f[i]=f[i-1];
        else f[i]=f[i-1]+f[i>>1];
    printf ("%d\n",f[n]);
    return 0;
}

三、P1044 [NOIP2003 普及组] 栈

  1. 问题：一个栈(无穷大)的进栈序列为1，2，3，…，n，有多少个不同的出栈序列?
  2. 分析：Catalan数，设f [ n ] 表示有n个数的出栈方案数。假设k是最后一个出栈的数，那么，在k之前，已经有 k - 1 个数进栈并出栈，方案数为 f [ k - 1 ]；此外，比k晚进栈且早出栈的有 n - k 个，方案数为 f [ n - k ]，所以一共有f [ k - 1 ] * f [ n - k ] 方案。当k取不同值时，产生的出栈序列是相互独立的，所以结果可以相加，k的取值为1~n，所以最终的答案为下式
  3. 边界：f [ 0 ] = f [ 1 ] = 1

  4. 代码：

      #include <cstdio>
  using namespace std;
  int n, f[20]={1,1};
  int main(){
      scanf ("%d",&n);
      for (int i=2;i<=n;i++)
          for (int j=0;j<n;j++)
              f[i]+=f[j]*f[i-1-j];
      printf ("%d\n", f[n]);        
      return 0;
  }

四、P1003 [NOIP2011 提高组] 铺地毯

代码：

    #include <cstdio>
    const int N=1e4+10;
    using namespace std;
    int n,a[N],b[N],g[N],k[N],ans,x,y;
    int main(){
        scanf ("%d",&n);
        for (int i=1;i<=n;i++)
            scanf ("%d%d%d%d",a+i,b+i,g+i,k+i);
        scanf ("%d%d",&x,&y);
        for (int i=1;i<=n;i++)
            if (x>=a[i]&&y>=b[i]&&x<=a[i]+g[i]&&y<=b[i]+k[i])
                ans=i;
        printf ("%d\n",ans);
        return 0;
    }