题解 CF746D 【Green and Black Tea】

• 2021 年 3 月 14 日
• 笔记
• Luogu Problems

题目分析

这道题表面上看上去挺简单，其实仔细研究一下还是值得钻研的。我本人做这道题使用的任然是$ DFS01 $背包。不过呢，与往常背包不同的是，这次递归中需要加许多参数。就数据强度来看，栈问题不大。

递归过程

我们使用一个栈以及两个临时栈。每次在里面$ push $当前的解。只有“G”与“B”。两个栈分别处理和红茶和和绿茶的情况。两种情况都要考虑到已经连续喝了几次某种茶。

在递归函数里，我们用到$ dep,s,g,h,last $ 这几个变量。分别代表深度、连续喝的总数、绿茶喝的总数、红茶喝的总数以及上次喝的茶是啥。$ 0 $代表绿茶，$1$代表红茶。

递归代码：

void dfs(int dep,int s,int g,int h,bool last)
{
if(dep>n)
{
stack<string>temp1=temp;
while(!temp1.empty())
{
cout<<temp1.top();
temp1.pop();
}
exit(0);
}
else
{
if(last==0)
{
temp.push("G");
if(g+1<=a)dfs(dep+1,s,g+1,h,!last);
if(s+1<=b&&s<k) dfs(dep+1,s+1,g,h+1,last);
else
{
cout<<"NO"<<endl;
exit(0);
}
}
else
{
temp.push("B");
if(s+1<=b)dfs(dep+1,s,g,h+1,!last);
if(g+1<=a&&s<k) dfs(dep+1,s+1,g,h,last);
else
{
cout<<"NO"<<endl;
exit(0);
}
}
}
if(!temp.empty()) temp.pop();
}

主函数

最后主函数的程序就简单了。像往常一样，$ dep $总是要是$ 1 $开始，其他都是$ 0 $；但是有一个问题，我们不仅要考虑第一次喝绿茶的情况，第一次还可能是红茶。所以我们在刚开始写递归函数的时候，我们需要递归两遍

主函数代码：

int main()
{
cin>>n>>k>>a>>b;
dfs(1,0,0,0,0);
dfs(1,0,0,0,1);
return 0;
}

完整代码

#include<bits/stdc++.h>
using namespace std;
int n,k,a,b;
stack<string>temp;
void dfs(int dep,int s,int g,int h,bool last)
{
if(dep>n)
{
stack<string>temp1=temp;
while(!temp1.empty())
{
cout<<temp1.top();
temp1.pop();
}
exit(0);
}
else
{
if(last==0)
{
temp.push("G");
if(g+1<=a)dfs(dep+1,s,g+1,h,!last);
if(s+1<=b&&s<k) dfs(dep+1,s+1,g,h+1,last);
else
{
cout<<"NO"<<endl;
exit(0);
}
}
else
{
temp.push("B");
if(s+1<=b)dfs(dep+1,s,g,h+1,!last);
if(g+1<=a&&s<k) dfs(dep+1,s+1,g,h,last);
else
{
cout<<"NO"<<endl;
exit(0);
}
}
}
if(!temp.empty()) temp.pop();
}
int main()
{
cin>>n>>k>>a>>b;
dfs(1,0,0,0,0);
dfs(1,0,0,0,1);
return 0;
}