当前位置:网站首页>2039: [蓝桥杯2022初赛] 李白打酒加强版 (动态规划)
2039: [蓝桥杯2022初赛] 李白打酒加强版 (动态规划)
2022-07-06 23:08:00 【疯疯癫癫才自由】
题目描述
话说大诗人李白,一生好饮。幸好他从不开车。
一天,他提着酒壶,从家里出来,酒壶中有酒 2 斗。他边走边唱:
无事街上走,提壶去打酒。
逢店加一倍,遇花喝一斗。
这一路上,他一共遇到店 N 次,遇到花 M 次。
已知最后一次遇到的是花,他正好把酒喝光了。
请你计算李白这一路遇到店和花的顺序,有多少种不同的可能?
注意:壶里没酒( 0 斗) 时遇店是合法的,加倍后还是没酒;但是没酒时遇花是不合法的。输入格式
输入包含多组测试数据。
第一行为T,表示存在T组测试数据,T不超过30。
对于每组测试数据,输入两个整数N 和M.
1 ≤ N, M ≤ 100。输出格式
输出一个整数表示答案。由于答案可能很大,输出模1000000007 的结果。
输入样例 复制
1 5 10
输出样例 复制
14
最开始是没写出来的,想的是深度优先搜索,也就是第二个代码,不能AC,后面看别人的推荐,才知道闫学灿(y总)(acwing网站的创始人,开了很多课,我相信有必要去看一看,慢慢的把数据结构学了,也得准备CCF的CSP认证了),看了他讲的蓝桥杯初赛,才搞懂了,从侧面也能看出,我很弱,emm,确实,革命尚未成功,我得继续努力。
分析:
状态设计:dp[i][j][k]的值表示遇到i家店,j朵花,酒壶中还剩k斗酒的可能情况数;
状态转移方程:dp[i][j][k]=dp[i-1][j][k/2](i>1&&k%2==0) + dp[i][j-1][k+1](j>1);
边界设计:除了dp[0][0][2]=1,其他元素全为0;
他一共遇到店 N 次,遇到花 M 次。已知最后一次遇到的是花, 他正好把酒喝光了;所以
最后一次肯定遇到的是花,那么最后的结果便是dp[N][M-1][1];
并且酒壶中酒的容量不能超过M;
/**
再编码:
状态设计:dp[i][j][k]的值表示遇到i家店,j朵花,酒壶中还剩k斗酒的可能情况数;
状态转移方程:dp[i][j][k]=dp[i-1][j][k/2](i>1&&k%2==0) + dp[i][j-1][k+1](j>1);
边界设计:除了dp[0][0][2]=1,其他元素全为0;
他一共遇到店 N 次,遇到花 M 次。已知最后一次遇到的是花, 他正好把酒喝光了;所以
最后一次肯定遇到的是花,那么最后的结果便是dp[N][M-1][1];
并且酒壶中酒的容量不能超过M;
*/
#include <cstdio>
#include <cstring>
using namespace std;
const int mod=1000000007;
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int n,m;
scanf("%d%d",&n,&m);
int dp[n+1][m+1][m+1];
memset(**dp,0,sizeof(dp));
dp[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 &val=dp[i][j][k];
if(i>=1&&k%2==0)
val=(val+dp[i-1][j][k/2])%mod;
if(j>=1)
val=(val+dp[i][j-1][k+1])%mod;
}
printf("%d\n",dp[n][m-1][1]);
}
return 0;
}
DFS解决
只能AC 13%,不得不说,对于一个问题,不能找到正确的算法策略与正确的算法策略
比较,可谓是天壤之别;
/**
DFS解决
只能AC 13%,不得不说,对于一个问题,不能找到正确的算法策略与正确的算法策略
比较,可谓是天壤之别;
*/
#include <iostream>
#include <cstdio>
using namespace std;
const int mod=1000000007;
void drink_DFS(int store,int flow,int drink);
int sum=0,N,M;
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
sum=0;
scanf("%d%d",&N,&M);
drink_DFS(0,0,2);
printf("%d\n",sum);
}
return 0;
}
void drink_DFS(int store,int flow,int drink)
{
if(drink < 0) return;
if(store > N || flow >= M) return;
if(drink>M) return;
if(store==N&&flow==M-1&&drink==1)
{
sum+=1;
sum%=mod;
return;
}
drink_DFS(store+1,flow,2*drink);
drink_DFS(store,flow+1,drink-1);
// store+=1;
// drink*=2;
// drink_DFS(store,flow,drink);
// store-=1;
// drink/=2;
// flow+=1;
// drink-=1;
// drink_DFS(store,flow,drink);
// flow-=1;
// drink+=1;
}
边栏推荐
- 3GPP信道模型路损基础知识
- Field data acquisition and edge calculation scheme of CNC machine tools
- ClickHouse(03)ClickHouse怎么安装和部署
- NiO related knowledge points (I)
- Servicemesh mainly solves three pain points
- Monitoring cannot be started after Oracle modifies the computer name
- HarmonyOS第四次培训
- Addressable 预下载
- Run the command once per second in Bash- Run command every second in Bash?
- Test interview | how much can you answer the real test interview question of an Internet company?
猜你喜欢
U++4 接口 学习笔记
qt 简单布局 盒子模型 加弹簧
【问道】编译原理
The sooner you understand the four rules of life, the more blessed you will be
【Android Kotlin协程】利用CoroutineContext实现网络请求失败后重试逻辑
当 Knative 遇见 WebAssembly
AttributeError: module ‘torch._ C‘ has no attribute ‘_ cuda_ setDevice‘
[hand torn STL] list
为什么很多人对技术债务产生误解
批量归一化(标准化)处理
随机推荐
Inventory host list in ansible (I wish you countless flowers and romance)
U++ game learning notes
最全常用高数公式
Redis如何实现多可用区?
3. Type of fund
npm ERR! 400 Bad Request - PUT xxx - “devDependencies“ dep “xx“ is not a valid dependency name
Talk about the importance of making it clear
Tree map: tree view - draw covid-19 array diagram
【PHP SPL笔记】
记录一次压测经验总结
Monitoring cannot be started after Oracle modifies the computer name
Addressable 预下载
Operand of null-aware operation ‘!‘ has type ‘SchedulerBinding‘ which excludes null.
Understand common network i/o models
【最佳网页宽度及其实现】「建议收藏」
JS variable plus
Why is the salary of test and development so high?
STM32F103ZE+SHT30检测环境温度与湿度(IIC模拟时序)
Time complexity & space complexity
Dynamically generate tables