当前位置:网站首页>2039: [Bluebridge cup 2022 preliminaries] Li Bai's enhanced version (dynamic planning)
2039: [Bluebridge cup 2022 preliminaries] Li Bai's enhanced version (dynamic planning)
2022-07-07 05:09:00 【Madness makes freedom】
Title Description
On the great poet Li Bai , Good drink for life . Fortunately, he never drives .
One day , He's carrying a jug , Come out of the house , There is wine in the wine pot 2 Bucket . He sang as he walked :
Walk on the street , Pick up the pot and go get the wine .
Double for every shop , Have a drink with flowers .
This way , He met the store N Time , Encounter flowers M Time .
We know that the last time we met was flowers , He just finished his drink .
Please calculate the order of shops and flowers Li Bai meets along the way , How many different possibilities ?
Be careful : There is no wine in the pot ( 0 Bucket ) Shiyu store is legal , There is still no wine after doubling ; But it's illegal to meet flowers without wine .Input format
Input contains multiple sets of test data .
First act T, Indicates presence T Group test data ,T No more than 30.
For each group of test data , Enter two integers N and M.
1 ≤ N, M ≤ 100.Output format
Output an integer for the answer . Because the answer can be big , Output mode 1000000007 Result .
sample input Copy
1 5 10
sample output Copy
14
It was not written at first , Think of depth first search , That is, the second code , You can't AC, See others' recommendations later , Just know Yan xuecan (y total )(acwing The founder of the website , There are many classes , I believe it is necessary to have a look , Slowly learn the data structure , You have to be prepared CCF Of CSP Certified ), I watched him talk about the preliminary match of the Blue Bridge Cup , Just understand , It can also be seen from the side , I'm weak ,emm, exactly , The revolution has not yet succeeded , I have to keep trying .
analysis :
State Design :dp[i][j][k] The value of indicates that i stores ,j A flower , There is still something left in the wine pot k The number of possible cases of fighting alcohol ;
State transition equation :dp[i][j][k]=dp[i-1][j][k/2](i>1&&k%2==0) + dp[i][j-1][k+1](j>1);
Boundary design : except dp[0][0][2]=1, All the other elements are 0;
He met the store N Time , Encounter flowers M Time . We know that the last time we met was flowers , He just finished his drink ; therefore
The last time I must encounter flowers , Then the final result is dp[N][M-1][1];
And the volume of wine in the wine pot cannot exceed M;
/**
Recode :
State Design :dp[i][j][k] The value of indicates that i stores ,j A flower , There is still something left in the wine pot k The number of possible cases of fighting alcohol ;
State transition equation :dp[i][j][k]=dp[i-1][j][k/2](i>1&&k%2==0) + dp[i][j-1][k+1](j>1);
Boundary design : except dp[0][0][2]=1, All the other elements are 0;
He met the store N Time , Encounter flowers M Time . We know that the last time we met was flowers , He just finished his drink ; therefore
The last time I must encounter flowers , Then the final result is dp[N][M-1][1];
And the volume of wine in the wine pot cannot exceed 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 solve
Can only AC 13%, Have to say , For a question , Unable to find the correct algorithm strategy and the correct algorithm strategy
Compare , It's a big difference ;
/**
DFS solve
Can only AC 13%, Have to say , For a question , Unable to find the correct algorithm strategy and the correct algorithm strategy
Compare , It's a big difference ;
*/
#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;
}
边栏推荐
- 【问道】编译原理
- Ansible中的inventory主機清單(預祝你我有數不盡的鮮花和浪漫)
- 01 machine learning related regulations
- Auto.js 获取手机所有app名字
- Error: No named parameter with the name ‘foregroundColor‘
- 基于Bevy游戏引擎和FPGA的双人游戏
- ThinkPHP关联预载入with
- SQL injection cookie injection
- Leetcode(417)——太平洋大西洋水流问题
- The sooner you understand the four rules of life, the more blessed you will be
猜你喜欢
随机推荐
STM32 system timer flashing LED
Flask project uses flask socketio exception: typeerror: function() argument 1 must be code, not str
Tree map: tree view - draw covid-19 array diagram
最长不下降子序列(LIS)(动态规划)
When knative meets webassembly
全国气象数据/降雨量分布数据/太阳辐射数据/NPP净初级生产力数据/植被覆盖度数据
app内嵌h5---iphone软键盘遮挡输入文字
Weebly mobile website editor mobile browsing New Era
最长回文子串(动态规划)
使用知云阅读器翻译统计遗传学书籍
全链路压测:影子库与影子表之争
STM32F103 realize IAP online upgrade application
AttributeError: module ‘torch._C‘ has no attribute ‘_cuda_setDevice‘
Ansible概述和模块解释(你刚走过了今天,而扑面而来的却是昨天)
Time complexity & space complexity
If you‘re running pod install manually, make sure flutter pub get is executed first.
2039: [蓝桥杯2022初赛] 李白打酒加强版 (动态规划)
SQL injection HTTP header injection
Timer创建定时器
Gavin teacher's perception of transformer live class - rasa project actual combat e-commerce retail customer service intelligent business dialogue robot microservice code analysis and dialogue experim