問題描述
話說大詩人李白, 一生好飲。幸好他從不開車。
一天, 他提著酒顯, 從家里出來, 酒顯中有酒 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 。
?
難。。
#include<iostream>
using namespace std;#define int long long
const int mod = 1000000007;
const int N = 110;int n, m;//dp[i][j][k]：遇到i次店，遇到j次花，剩余酒量為k時的順序數量
int dp[N][N][N]; signed main()
{cin>>n>>m;dp[0][0][2] = 1; //遇到店的數量for(int i=0; i<=n; ++i) {//遇到的花的次數for(int j=0; j<=m-1; ++j)//因為最后一次是花，所以之前最多遇到 m-1 次花{//遍歷當前剩余的酒量//因為每次遇花喝一斗，最多喝 m 斗，所以酒量不會超過 mfor(int k=0; k<=m; ++k){//遇到花 if(j>=1 && k>=1) //j>=1：j-1>=0， k>=1：當前酒量至少為1斗{//逆向邏輯：花的總次數從j-1增加到j，酒量從k+1減少到kdp[i][j][k] = dp[i][j-1][k+1]; //單純的賦值，數值不會增長，因此不需要取模}//遇到店 if(i>=1 && k%2==0){//逆向邏輯：店的總次數從i-1增加到i，酒量從k/2加倍到kdp[i][j][k] = (dp[i][j][k] + dp[i-1][j][k/2]) % mod; //加法操作，數值會增長，必須取模}}}}//遇到 n 次店，m - 1 次花，酒量為1斗的方案數cout<<dp[n][m-1][1];return 0;
}
