算法1
#include<bits/stdc++.h>
using namespace std;
const int N=110;
const int MOD=1e9+7;
int n,m;
int f[N][N][N];//状态第i个店,j个花,k斗酒
int main()
{
cin>>n>>m;
f[0][0][2]=1;//初始为1
for(int i=0;i<=n;i++)//n个店
{
for(int j=0;j<=m;j++)//m个花
{
for(int k=0;k<=m;k++)//k斗酒,k在0和m之间
{
int &v=f[i][j][k];//记得修改符&
//cout<<v<<endl;
if(i>=1&&k%2==0)v=(v+f[i-1][j][k/2])%MOD;//如果倒数第二个遇到的是店,前一个状态就是i-1店,然后j花,k/2斗酒
if(j>=1)v=(v+f[i][j-1][k+1])%MOD;//如果倒数第二个是花,那么前一个状态是i店,j-1花,k+1斗酒
}
}
}
cout<<f[n][m-1][1];//因为最后遇到花,那么求倒数第二种状态集合即可,那么就是n店,m-1花,1斗酒
return 0;
}
算法二
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=110,mod=1e9+7;
int n,m;
int f[N][N][N];
int main()
{
cin>>n>>m;
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];
if(i&&k%2==0) v=(v+f[i-1][j][k/2])%mod;
if(j) v=(v+f[i][j-1][k+1]) %mod;
}
cout<<f[n][m-1][1]<<endl;
return 0;
}
算法三
参考链接
#include<bits/stdc++.h>
using namespace std;
const int N = 110, M = 1000000007;
int n, m, f[N][N][N][2];
int main()
{
scanf("%d%d", &m, &n);
for(int i = 0; i <= n; i ++ )
{
for(int j = 0; j <= m; j ++ )
{
for(int k = 0; k < 100; k ++ )
{
for(int c = 0; c < 2; c ++ )
{
if(i == 0 && j == 0 && k == 2 && c == 1)
f[i][j][k][c] = 1;
if(i == 0 && j == 0)
continue;
if(j > 0 && c == 1 && k % 2 == 0)
{
f[i][j][k][c] = (f[i][j - 1][k / 2][0] + f[i][j - 1][k / 2][1]) % M;
}
if(i > 0 && c == 0 && k >= 0)
{
f[i][j][k][c] = (f[i - 1][j][k + 1][0] + f[i - 1][j][k + 1][1]) % M;
}
}
}
}
}
printf("%d", f[n][m][0][0]);
return 0;
}