李白打酒dfs&&DP
发现这题的dfs平台没多少分,但按照考试能拿40%的分数,OJ只能过3个测试点。
不过这不失为一个练习回溯的好题,下面是按照朴素模板写的dfs写法,测试请将vector数组部分删去。
#include <bits/stdc++.h>
using namespace std;
vector <int> V;//保存路径
int n,m; // 最大走n个1,m个0
long long cnt =0;
void dfs(int sp,int wn,int cs,int n_cnt,int m_cnt)
{
//步数、酒量、当前步数的选择、记录走了多少个1、记录走了多少个0
// 终止状态
if(sp>=m+n && cs==0 && wn==0 && n_cnt==n && m_cnt ==m)
{
for(auto v:V)
{
cout << v;
}
cout << endl;
cnt++; //记录一个
cnt%=1000000007;
return;
}
// 枚举方法(可以不用for,这里为了体现模板)
for(int i=0;i<2;i++){
if(wn>=0 && n_cnt<=n && m_cnt<=m){ // 可以枚举的条件(入栈的条件)
if(i==0){
V.push_back(i); // 进入候选
m_cnt++; // 计数
dfs(sp+1,wn-1,0,n_cnt,m_cnt); // 压栈
V.pop_back(); //回溯
m_cnt--; //回溯
}
if(i==1){
V.push_back(i);
n_cnt++;
dfs(sp+1,wn*2,1,n_cnt,m_cnt);
V.pop_back();
n_cnt--;
}
}
}
}
int main()
{
cin >> n >> m;
dfs(0,2,-1,0,0);
cout << cnt << endl;
}
DP写法
分析:某一个状态:
n_cnt m_cnt wn是可以被转换的
将它枚举为两种:n_cnt-1 m_cnt wn/2 || n_cnt m_cnt-1 wn+1
因为是方法数,所以他们的连接用
dp(n_cnt m_cnt wn) = dp(n_cnt-1 m_cnt wn/2)+dp(n_cnt m_cnt-1 wn+1)
注意一点wn必须是偶数,否则无法公式转换为dp(n_cnt m_cnt wn) = dp(n_cnt m_cnt-1 wn+1)
代码如下:
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 110, MOD = 1000000007;
int f[N][N][N]; // i家店,j朵花,k斗酒
int n, m;
// f n m 0 && 结尾是花 等价于 f n m-1 0+1
int main()
{
cin >> n >> m;
f[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++) //酒不能超过m
{
if (i!=0 && k % 2 == 0) //酒店下标合法,且酒数量为偶数
{
f[i][j][k] += f[i-1][j][k/2];
f[i][j][k] %= MOD;
}
if (j!=0)
{
f[i][j][k] += f[i][j-1][k+1] ;
f[i][j][k] %= MOD;
}
}
cout << f[n][m-1][1] << endl;
return 0;
}