SCU training contest 3 D、化学品问题 II

1、DP。。。不多说，注意就是要排除最后为m个1且m个1前有一个0的状况。（如果不是在最后放上1导致有m个1的话，早在dp（i-1）就不合法了）。

#include<cstdio>

#include<cstring>

using namespace std;

int d[50],m,f[50];

int dp(int n){

    int &ans=d[n];

 if(n==0) ans=1;

 if(ans>=0) return ans;

 if(n<m) return f[n];

 else if(n==m) return f[n]-1;

 else ans=dp(n-1)*2-dp(n-m-1);

 return ans;

}

int main(){

   int L,n;

   scanf("%d",&L);

   f[1]=2;

   for(int i=2;i<=30;i++){

       f[i]=f[i-1]*2;

   }

   for(int i=0;i<L;i++){

      scanf("%d%d",&n,&m);

   memset(d,-1,sizeof(d));

   printf("%d\n",dp(n));

   }

   return 0;

}