acwing4408李白打酒

• 要点
  • 状态转移一般都是从最后一步来考虑的
  • 题目中有动态变化的元素，这是转移的要点

思路：这是一道状态机题目，要把三种状态都用数组表示出来，所以要三维

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=210,MOD=1000000007;
int f[N][N][N];
//f[i][j][k]表示走过i个花，j个店，还剩下k壶酒的方案数
int main()
{int n,m;cin >> n >> m;f[0][0][2]=1;//初始化，表示刚开始时有两壶酒的方案数为1，即只有这种方案for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){for(int k=0;k<=100;k++){if(i>0) f[i][j][k]=(f[i][j][k]+f[i-1][j][k+1])%MOD;//最后一步为花if(j>0 && k%2==0) f[i][j][k]=(f[i][j][k]+f[i][j-1][k/2])%MOD;//最后一步为店}}}//最后不能直接输出f[n][m][0]，因为这样就无法确定最后一步是不是花，所以我们要往前推一步cout << f[n-1][m][1];return 0;
}