AcWing 4408. 李白打酒加强版
原题链接
中等
作者:
周夏柒
,
2024-03-30 14:06:26
,
所有人可见
,
阅读 2
import java.util.*;
public class Main{
static int mods=1000000007;
static int N=110;
static int f[][][]=new int[N][N][N];
public static void main(String []args){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int m=sc.nextInt();
f[0][0][2]=1;
for(int i=0;i<=n;i++){
//店数最多为n,i最多为n
for(int j=0;j<=m;j++){
//花数最多为m,j最多为m
for(int k=0;k<=m;k++){
//走到最后的花,酒最多为m。
//最后为店的方案数
if(i>=1&&k%2==0)f[i][j][k]+=f[i-1][j][k/2]%mods;
//最后为花的方案数
if(j>=1)f[i][j][k]+=f[i][j-1][k+1]%mods;
}
}
}
//倒推倒数第二个状态
//最后一站是花,走到最后一站前酒还剩1斗。
System.out.println(f[n][m-1][1]);
}
}