题目描述
话说大诗人李白，一生好饮。幸好他从不开车。
一天，他提着酒壶，从家里出来，酒壶中有酒 2 斗。他边走边唱：
无事街上走，提壶去打酒。
逢店加一倍，遇花喝一斗。
这一路上，他一共遇到店 N 次，遇到花 M 次。已知最后一次遇到的是花， 他正好把酒喝光了。
请你计算李白这一路遇到店和花的顺序，有多少种不同的可能？
注意：壶里没酒 ( 0 斗) 时遇店是合法的，加倍后还是没酒；但是没酒时遇花是不合法的。
输入格式
第一行包含两个整数 N 和 M.
输出格式
输出一个整数表示答案。由于答案可能很大，输出模 1000000007 的结果。
样例输入
5 10
样例输出
14
提示
如果我们用 0 代表遇到花，1 代表遇到店，14 种顺序如下：
010101101000000
010110010010000
011000110010000
100010110010000
011001000110000
100011000110000
100100010110000
010110100000100
011001001000100
100011001000100
100100011000100
011010000010100
100100100010100
101000001010100
对于 40% 的评测用例：1 ≤ N, M ≤ 10。
对于 100% 的评测用例：1 ≤ N, M ≤ 100。
DFS (通过64%，ACwing 3/11）;
#include<iostream>
using namespace std;
#define int long long
int mod=1000000007;
int n,m;
int ans=0;
void dfs(int cnt,int x,int y){
if(cnt<0) return ;
if(y==m+1){
if(x==n+1&&cnt==0){
ans++;
ans%=mod;
// cout<<cnt<<' '<<m-y<<"---"<<endl;
}
return ;
}
if(cnt>m-y+1||n-x>=m-y) return ;
if(y>m+1||x>n+1) return ;
dfs(cnt*2,x+1,y);
dfs(cnt-1,x,y+1);
}
signed main(){
scanf("%d%d",&n,&m);
dfs(2,1,1);
cout<<ans%mod<<endl;
return 0;
}DFS(AC)
#include<iostream>
#include<cstring>
using namespace std;
#define int long long
const int N=110;
int mod=1000000007;
int n,m;
int ans=0;
int arr[N][N][N];
int dfs(int n,int m,int cnt){
if(m<0||n<0) return 0;
if(arr[n][m][cnt]!=-1) return arr[n][m][cnt];
if(cnt<0) return 0;
if(m==0){
if(n==0&&cnt==0) return 1;
return 0;
}
if(cnt>m||n>=m) return 0;
ans=dfs(n-1,m,cnt*2)+dfs(n,m-1,cnt-1);
ans%=mod;
arr[n][m][cnt]=ans;
return ans;
}
signed main(){
memset(arr,-1,sizeof arr);
scanf("%d%d",&n,&m);
cout<<dfs(n,m,2)<<endl;
return 0;
}DP（AC）
f[i][j][k]：走到了第i个位置，遇到了j个花，还剩k斗酒的合法方案数.
#include<iostream>
using namespace std;
#define int long long
const int N=110;
int f[N*2][N][N*2];
int mod=1000000007;
signed main(){
int n,m;
cin>>n>>m;
f[0][0][2]=1;
for(int i=1;i<n+m;i++){
for(int j=0;j<m;j++){
for(int k=0;k<=m;k++){
//k为偶数，第i个可以是店，也可以是花，k为奇数，只能是花
if(k%2==0){
//店转移
f[i][j][k]=(f[i][j][k]+f[i-1][j][k>>1])%mod;
}
//花转移
if(j>=1) f[i][j][k]=(f[i][j][k]+f[i-1][j-1][k+1])%mod;
}
}
}
cout<<f[n+m-1][m-1][1]<<endl;
return 0;
}