很明显的DP但是要注意的东西很多。不能盲目初始化,另外看的DP课件说的就是DP的特征,最优子结构,最优局部特性。找到DP的关键就在这里。
/*
ID:nocows
LANG:C++
PROG:nocows
*/
#include<stdio.h>
#define MAXN 201
#define MAXK 101
#define mod 9901
using namespace std;int main()
{freopen( "nocows.in","r",stdin );freopen( "nocows.out","w",stdout );int N,K;int DP[MAXN][MAXK];scanf( "%d %d",&N,&K );for( int i=0;i<=N;i++ )for( int j=0;j<=K;j++ )DP[i][j]=0;for( int i=1;i<=K;i++ )DP[1][i]=1;for( int i=1;i<=K;i++ )for( int j=3;j<=N;j+=2 )for( int k=1;k<j;k+=2 )DP[j][i]=(DP[j][i]+DP[k][i-1]*DP[j-k-1][i-1])%mod;printf( "%d\n",(DP[N][K]-DP[N][K-1]+mod)%mod );return 0;
}