AcWing 4408. 李白打酒加强版
原题链接
中等
作者:
a行君
,
2024-04-01 23:15:29
,
所有人可见
,
阅读 3
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110;
const int M =1000000007;
int dp[N][N][100][2]; //分别为花,店,手中酒,目前状态
int main()
{
int n,m;
cin >> n>>m;
dp[0][0][2][1]=1;
for (int i = 0; i <= m; i ++ ){
for (int j = 0; j <= n; j ++ ){
for (int k = 0; k < 100; k ++ ){
for (int h = 0; h < 2; h ++ ){
if(i == 0 && j == 0)
continue;
if(j > 0 && h == 1 && k % 2 == 0)
dp[i][j][k][h] = dp[i][j-1][k/2][0]+dp[i][j-1][k/2][1] ;
if(i > 0 && h == 0 && k >= 0)
dp[i][j][k][h] = dp[i-1][j][k+1][0]+dp[i-1][j][k+1][1];
dp[i][j][k][h]=dp[i][j][k][h]%M;
}
}
}
}
cout << dp[m][n][0][0];
return 0;
}