李白打酒加强版 -- 题解 c++

题目链接 : 

4408. 李白打酒加强版 - AcWing题库

用户登录

二进制搜索

只能过10%,极限暴力

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
typedef long long LL;
const int mod = 1e9+7;
const int N = 2e5+10;
using namespace std;int n , m , p ;string f(int x){string s = bitset<32>(x).to_string() ;return s.substr(16) ;
}int get(LL x){int cnt = 0 ;while(x){x = x & (x-1) ;cnt ++ ;}return cnt  ;
}bool pd(int x){if(get(x)!=n) return false ;int f = 2 ;for(int i=p-1;i>=0;i--){if((x>>i)&1) f *= 2 ;else{if(f==0) return false ;f--;}}if(f==0) return true ;else return false ;
}inline void solve(){cin >> n >> m ;p = n + m ;// 0 : 花 ， 1 ： 酒 LL ans = 0 ;for(int i=0;i<(1<<p);i++){if(pd(i)){ans ++ ;
//			cout << f(i) << endl ;}}cout << ans << endl ;	 
}signed main()
{IOSint _ = 1;while(_ --) solve();return 0;
}

DFS

没啥好讲的，直接看代码，能过、40%

#include<bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7 ;
typedef long long LL;
int n , m ;
LL ans ;void dfs(int i,int j,int k,int z){//i次店，j次花，剩余k酒，z:当前位置//最后一次必为花，且酒刚好为0if(z==n+m-1){//倒数第二次if(k==1&&i==n&&j==m-1){ans ++ ;}return ;}if(k<=0) return ;// 遇到店dfs(i+1,j,k*2,z+1);//遇到花dfs(i,j+1,k-1,z+1);
}int main(){cin >> n >> m ; // 店n次，花m次dfs(0,0,2,0);ans = ans % MOD ;cout << ans << endl ;return 0 ;
}

DP

dp[i][j][k] 表示为前i次，有j次遇到店，剩下酒为k斗 的方案数

详细请看题解

#include<bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7 ;
const int N = 201 ;
typedef long long LL;
int n , m ;
LL ans ;
LL dp[N][N][N] ;// dp[i][j][k] 表示为前i次，有j次遇到店，剩下酒为k斗 的方案数int main(){cin >> n >> m ; // 店n次，花m次dp[0][0][2] = 1 ;//初始2for(int i=1;i<=n+m;i++){for(int j=0;j<=n;j++){for(int k=0;k<=100;k++){//最多消耗100瓶// 上一次遇到花dp[i][j][k] += dp[i-1][j][k+1];// 上一次遇到酒if(j && k%2==0){dp[i][j][k] += dp[i-1][j-1][k/2] ;}dp[i][j][k] %= MOD ;}}}dp[n+m][n][0] = dp[n+m-1][n][1] ;cout << dp[n+m][n][0] << endl ;return 0 ;
}