微网站开发需求文档,互联网上市公司一览表,如何设计与制作网页,wordpress本地【题目描述】
话说大诗人李白#xff0c;一生好饮。
幸好他从不开车。
一天#xff0c;他提着酒壶#xff0c;从家里出来#xff0c;酒壶中有酒 2 斗。
他边走边唱#xff1a;
无事街上走#xff0c;提壶去打酒。
逢店加一倍#xff0c;遇花喝一斗。
这一路上一生好饮。
幸好他从不开车。
一天他提着酒壶从家里出来酒壶中有酒 2 斗。
他边走边唱
无事街上走提壶去打酒。
逢店加一倍遇花喝一斗。
这一路上他一共遇到店 N 次遇到花 M 次。
已知最后一次遇到的是花他正好把酒喝光了。
请你计算李白这一路遇到店和花的顺序有多少种不同的可能
注意壶里没酒 (0 斗) 时遇店是合法的加倍后还是没酒但是没酒时遇花是不合法的。
【输入格式】
第一行包含两个整数 N 和 M。
【输出格式】
输出一个整数表示答案。由于答案可能很大输出模 1000000007 的结果。
【数据范围】
对于 40% 的评测用例1≤N,M≤10。 对于 100% 的评测用例1≤N,M≤100。
【输入样例】 5 10 【输出样例】 14 【样例解释】
如果我们用 0 代表遇到花1 代表遇到店14 种顺序如下 010101101000000 010110010010000 011000110010000 100010110010000 011001000110000 100011000110000 100100010110000 010110100000100 011001001000100 100011001000100 100100011000100 011010000010100 100100100010100 101000001010100 【思路】
关键是酒的数量不可能多于遇到花的次数否则不可能喝光酒。
状态表示f[i][j][k]i 表示当前遇到店的数量、j 表示当前遇到花的数量k 表示当前酒的数量。
状态属性当前所有数量的集合。
状态表示当前f[i][j][k]刚遇到店还是刚遇到花f[i][j][k] f[i-1][j][k/2] f[i][j-1][k1]
【代码】
#include iostream
#include cstring
#include algorithmusing namespace std;const int N 110, MOD 1e9 7;int n, m;
int f[N][N][N];int main()
{cin n m;//初始状态没遇到店和花有2斗酒f[0][0][2] 1;for (int i 0; i n; i )for (int j 0; j m; j )for (int k 0; k m; k ){//把当前值赋给变量是为了代码简洁需要加上 才能保证取出原数组中元素的地址。int v f[i][j][k];//刚遇到的是店需要判断 i 1 并且花是偶数if (i k % 2 0) v (v f[i - 1][j][k / 2]) % MOD;//刚遇到的是花需要判断 j 1if (j) v (v f[i][j - 1][k 1]) % MOD;}//最后的状态即为遇到花后酒刚好喝完。cout f[n][m - 1][1] endl;return 0;
}
