李白打酒加强版
题目描述
话说大诗人李白,一生好饮。幸好他从不开车。
一天,他提着酒壶,从家里出来,酒壶中有酒 2 斗。他边走边唱:
无事街上走,提壶去打酒。
逢店加一倍,遇花喝一斗。
这一路上,他一共遇到店 N 次,遇到花 M 次。
已知最后一次遇到的是花,他正好把酒喝光了。
请你计算李白这一路遇到店和花的顺序,有多少种不同的可能?
注意:壶里没酒( 0 斗) 时遇店是合法的,加倍后还是没酒;但是没酒时遇花是不合法的。
输入格式
输入包含多组测试数据。
第一行为T,表示存在T组测试数据,T不超过30。
对于每组测试数据,输入两个整数N 和M.
1 ≤ N, M ≤ 100。
输出格式
输出一个整数表示答案。由于答案可能很大,输出模1000000007 的结果。
输入样例
5 10
输出样例
14
动态规划dp
思路:a[i][j][k]表示走到了第i家店,遇到了j朵花,酒的数量为k,然后就可以转移了文章来源:https://www.toymoban.com/news/detail-412052.html
- f(i - 1, j, k / 2):遇到的是店,说明此前遇到店的数量为i - 1,遇到花的数量仍然为j,酒壶中酒的数量为k/2;满足条件i大于等于1,k能被二整除
- f(i, j - 1, k + 1):遇到的是花,说明此前遇到店的数量为i,遇到花的数量为j - 1,酒壶中酒的数量为k + 1。满足条件j大于等于1
注意转移的条件,然后i和j要从0开始遍历,还有结果是
a[n][m-1][1]才能保证最后一个是花且刚好酒为0文章来源地址https://www.toymoban.com/news/detail-412052.html
#include <bits/stdc++.h>
using namespace std;
int a[105][105][105];
const int MOD=1e9+7;
int main()
{
int n,m;
cin>>n>>m;
a[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++)
{
if(i>=1&&k%2==0) a[i][j][k]=(a[i][j][k]+a[i-1][j][k/2])%MOD;
if(j>=1) a[i][j][k]=(a[i][j][k]+a[i][j-1][k+1])%MOD;
}
}
}
cout<<a[n][m-1][1]<<endl;
return 0;
}
到了这里,关于I 李白打酒加强版 / 动态规划dp的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!