暴力骗分+dfs剪叶+动态规划

解题思路:

注意事项:

参考代码:

//李白打酒加强版 

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <math.h>

#define N  200

#define mod  1000000007

int n=0,m=0;

long long me[N][N][N];//记忆化搜索 剪枝手段 

long long dp[N][N][N];

int baolijianyan(long long x){

int t=0,s=1,n1=0,m1=0;

for(int i=0;i<n+m-1;i++){

t=x%2;

if(t==0){s++;m1++;if(m1>m-1){return 0;}}

else if(t==1){if(s&1){return 0;}else {s/=2;n1++;if(n1>n){return 0;}}}

x/=2;

}

    if((s==2)&&(n1==n)&&(m1==m-1)){return 1;}

}

long long  baoli(int n,int m){

long long i=0,s=0;

for(i=0;i<(1<<(n+m-1));i++){

if(baolijianyan(i)){s++;s%=mod;}

}

printf("%lld",s);

}

//long long me[N][N][N];//记忆化搜索 剪枝手段 

long long dfs(int x,int y,int j){

if(x>=0&&y>=0&&j>=0&&x<N&&y<N&&j<N)//防止数组越界 

{if(me[x][y][j]!=-1) return me[x][y][j];

if(x==0&&y==1&&j==1){

me[x][y][j]=1;

return 1;

}

if(y==0||j==0||j>y){me[x][y][j]=0;return 0;}

long long k1=(dfs(x-1,y,j*2))%mod;

long long k2=(dfs(x,y-1,j-1))%mod;

me[x][y][j]=(k1+k2)%mod;

return me[x][y][j];

}

else return 0;

}

int main (){

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

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

//baoli(n,m);

//printf("%lld",dfs(n,m,2));

dp[0][0][2]=1;

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

for(int j=0;j<=m;j++){

for(int k=0;k<=m-j;k++){

if((!(k&1))&&k!=0&&i>=1){dp[i][j][k]+=dp[i-1][j][k>>1];}

if(j>=1){dp[i][j][k]+=dp[i][j-1][k+1];}

dp[i][j][k]%=mod;

}

}

}

printf("%lld",dp[n][m][0]);

return  0 ;

}