广州企业网站建设哪家服务好,网站优化推广服务,企业网站维护工作,郑州网站建设 股权投资题目描述
话说大诗人李白#xff0c;一生好饮。幸好他从不开车。
一天#xff0c;他提着酒壶#xff0c;从家里出来#xff0c;酒壶中有酒 2 斗。他边走边唱#xff1a;
无事街上走#xff0c;提壶去打酒。
逢店加一倍#xff0c;遇花喝一斗。
这一路上#xff0c…题目描述
话说大诗人李白一生好饮。幸好他从不开车。
一天他提着酒壶从家里出来酒壶中有酒 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;
#includeiostream
using namespace std;
#define int long long
int mod1000000007;
int n,m;
int ans0;
void dfs(int cnt,int x,int y){if(cnt0) return ;if(ym1){if(xn1cnt0){ans;ans%mod;// coutcnt m-y---endl;}return ;}if(cntm-y1||n-xm-y) return ;if(ym1||xn1) return ;dfs(cnt*2,x1,y);dfs(cnt-1,x,y1);
}
signed main(){scanf(%d%d,n,m);dfs(2,1,1);coutans%modendl;return 0;
}
DFS(AC)
#includeiostream
#includecstring
using namespace std;
#define int long long
const int N110;
int mod1000000007;
int n,m;
int ans0;
int arr[N][N][N];
int dfs(int n,int m,int cnt){if(m0||n0) return 0;if(arr[n][m][cnt]!-1) return arr[n][m][cnt];if(cnt0) return 0;if(m0){if(n0cnt0) return 1;return 0;}if(cntm||nm) return 0;ansdfs(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);coutdfs(n,m,2)endl;return 0;
}
DPAC
f[i][j][k]走到了第i个位置遇到了j个花还剩k斗酒的合法方案数.
#includeiostream
using namespace std;
#define int long long
const int N110;
int f[N*2][N][N*2];
int mod1000000007;
signed main(){int n,m;cinnm;f[0][0][2]1;for(int i1;inm;i){for(int j0;jm;j){for(int k0;km;k){//k为偶数第i个可以是店也可以是花k为奇数只能是花if(k%20){//店转移f[i][j][k](f[i][j][k]f[i-1][j][k1])%mod;}//花转移if(j1) f[i][j][k](f[i][j][k]f[i-1][j-1][k1])%mod;}}}coutf[nm-1][m-1][1]endl;return 0;
}
