题目链接 :
二进制搜索
只能过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()
{
IOS
int _ = 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:当前位置
//最后一次必为花,且酒刚好为0
if(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 ;//初始2
for(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 ;
}