题解 CF746D 【Green and Black Tea】

题目分析

这道题表面上看上去挺简单,其实仔细研究一下还是值得钻研的。我本人做这道题使用的任然是$ 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;
}

给TA买糖
共{{data.count}}人
人已赞赏
经验教程

家穷应该读大学吗?| 寒门学子的奋斗史(一)

2021-3-14 18:43:00

经验教程

一键部署!这样搭建一个文档网站真的很简单!

2021-3-14 19:15:00

⚠️
免责声明:根据《计算机软件保护条例》第十七条规定“为了学习和研究软件内含的设计思想和原理,通过安装、显示、传输或者存储软件等方式使用软件的,可以不经软件著作权人许可,不向其支付报酬。”您需知晓本站所有内容资源均来源于网络,仅供用户交流学习与研究使用,版权归属原版权方所有,版权争议与本站无关,用户本人下载后不能用作商业或非法用途,需在24个小时之内从您的电脑中彻底删除上述内容,否则后果均由用户承担责任;如果您访问和下载此文件,表示您同意只将此文件用于参考、学习而非其他用途,否则一切后果请您自行承担,如果您喜欢该程序,请支持正版软件,购买注册,得到更好的正版服务。 本站为个人博客非盈利性站点,所有软件信息均来自网络,所有资源仅供学习参考研究目的,并不贩卖软件,不存在任何商业目的及用途,网站会员捐赠是您喜欢本站而产生的赞助支持行为,仅为维持服务器的开支与维护,全凭自愿无任何强求。本站部份代码及教程来源于互联网,仅供网友学习交流,若您喜欢本文可附上原文链接随意转载。
无意侵害您的权益,请发送邮件至 momeis6@qq.com 或点击右侧 私信:momeis 反馈,我们将尽快处理。
0 条回复 A文章作者 M管理员
    暂无讨论,说说你的看法吧
个人中心
今日签到
有新私信 私信列表
搜索