[{"createTime":1735734952000,"id":1,"img":"hwy_ms_500_252.jpeg","link":"https://activity.huaweicloud.com/cps.html?fromacct=261f35b6-af54-4511-a2ca-910fa15905d1&utm_source=V1g3MDY4NTY=&utm_medium=cps&utm_campaign=201905","name":"华为云秒杀","status":9,"txt":"华为云38元秒杀","type":1,"updateTime":1735747411000,"userId":3},{"createTime":1736173885000,"id":2,"img":"txy_480_300.png","link":"https://cloud.tencent.com/act/cps/redirect?redirect=1077&cps_key=edb15096bfff75effaaa8c8bb66138bd&from=console","name":"腾讯云秒杀","status":9,"txt":"腾讯云限量秒杀","type":1,"updateTime":1736173885000,"userId":3},{"createTime":1736177492000,"id":3,"img":"aly_251_140.png","link":"https://www.aliyun.com/minisite/goods?userCode=pwp8kmv3","memo":"","name":"阿里云","status":9,"txt":"阿里云2折起","type":1,"updateTime":1736177492000,"userId":3},{"createTime":1735660800000,"id":4,"img":"vultr_560_300.png","link":"https://www.vultr.com/?ref=9603742-8H","name":"Vultr","status":9,"txt":"Vultr送$100","type":1,"updateTime":1735660800000,"userId":3},{"createTime":1735660800000,"id":5,"img":"jdy_663_320.jpg","link":"https://3.cn/2ay1-e5t","name":"京东云","status":9,"txt":"京东云特惠专区","type":1,"updateTime":1735660800000,"userId":3},{"createTime":1735660800000,"id":6,"img":"new_ads.png","link":"https://www.iodraw.com/ads","name":"发布广告","status":9,"txt":"发布广告","type":1,"updateTime":1735660800000,"userId":3},{"createTime":1735660800000,"id":7,"img":"yun_910_50.png","link":"https://activity.huaweicloud.com/discount_area_v5/index.html?fromacct=261f35b6-af54-4511-a2ca-910fa15905d1&utm_source=aXhpYW95YW5nOA===&utm_medium=cps&utm_campaign=201905","name":"底部","status":9,"txt":"高性能云服务器2折起","type":2,"updateTime":1735660800000,"userId":3}]
输出答案对1e9+7取模
样例输入
5 10
样例输出
14
分析：这是一道动态规划题，设f[i][j][k]表示走到了第i个位置，遇到了j个花，还剩k斗酒的合法方案数.
初始化很简单就是f[0][0][2]=1,因为一开始酒的数量是2
假如共遇到店n次，遇到花m次：
那么答案就是f[n+m-1][m-1][1]
,这是很容易理解的，因为我们共需要遇到m次花且最后一次一定是花，则走到倒数第二个位置时一定已经遇到了m-1个花，且由于遇到花后酒的数量会减少1，所以走到倒数第二个位置时酒的数量也必须是1.
下面开始进行状态转移方程的推导：
首先我们有必要对酒的奇偶性进行讨论，因为当走到第i个位置时酒的数量为偶，则第i个位置不可能为店，因为无论是奇数还是偶数，乘以2得到的数都是一个偶数，所以只有当k是偶数时第i个位置才可能是店，假如第i个位置是店，那么这个时候在第i-1个位置的酒的数量就是k/2，而遇到花的数量跟第i-1个位置是一样的都是j，这个很好理解，下面再看一下第i个位置是花的情况，那么第i-1个位置的酒的数量一定是k+1，因为在第i个位置消耗了1，而到达第i个位置遇到的花的数量就要比第i-1个位置遇到花的数量多1，因为我们现在是在假设第i个位置是花。
这就是这道题目的全部分析过程了，下面给出代码：
#include<iostream> #include<algorithm> #include<cstdio> #include<cstring>
#include<set> #include<vector> #include<map> #include<queue> using namespace
std; const int N=113; const int mod=1e9+7; long long
f[N*2][N][N];//f[i][j][k]表示走到了第i个位置，遇到了j个花，还剩k斗酒的合法方案数 int main() {
f[0][0][2]=1;//初始化 int n,m; cin>>n>>m; for(int i=1;i<n+m;i++) for(int
j=0;j<m;j++) for(int k=0;k<=m;k++)//酒的数量不能超过花的数量，否则就算之后一直是花也喝不完 {
if(!(k&1))//k是偶数，则第i个位置可以是店，否则不可以是店
f[i][j][k]=(f[i][j][k]+f[i-1][j][k>>1])%mod; if(j>=1)//无论k是奇数还是偶数，第i个位置都可以是花
f[i][j][k]=(f[i][j][k]+f[i-1][j-1][k+1])%mod; }
printf("%lld",f[n+m-1][m-1][1]); return 0; }
