题目描述
李白打酒
dfs暴力骗分 蓝桥杯上可以过40%
不会dp能拿这么多很划算了
C++ 代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m;
int ans=0;
void dfs(int i,int k,int d,int h)//遇店d 遇花 h i是当前位置 k剩余酒量
{
if(d>n || h>m) return; //花或店大于总量直接返回
if(i==m+n-1 && d==n && h==m-1 && k==1)//倒数第二个位置 店的数量为n 花的数量为m-1 并且还剩下1的数量的酒
{
ans++;//答案加加
return;
}
if(k<=0) return;//要是就量小于等于0 直接返回
dfs(i+1,k-1,d,h+1);//遇花
dfs(i+1,2*k,d+1,h);//遇店
}
signed main()
{
cin>>n>>m;
dfs(0,2,0,0);//初始化
cout<<ans%1000000007;
return 0;
}
好爽