【洛谷 P2089】烤鸡(深度优先搜索)

简介: ## 摘要:猪猪Hanke的烤鸡问题要求找出所有配料组合,使得$10$种配料(每种$1$到$3$克)的总和等于给定美味程度$n$。输入为正整数$n$,输出为方案总数及所有符合条件的配料分配,按字典序排列。样例输入$11$,输出$10$种方案。代码采用递归搜索,先计数再打印方案。$n\leq5000$时保证数据覆盖。

烤鸡

题目背景

猪猪 Hanke 得到了一只鸡。

题目描述

猪猪 Hanke 特别喜欢吃烤鸡(本是同畜牲,相煎何太急!)Hanke 吃鸡很特别,为什么特别呢?因为他有 $10$ 种配料(芥末、孜然等),每种配料可以放 $1$ 到 $3$ 克,任意烤鸡的美味程度为所有配料质量之和。

现在, Hanke 想要知道,如果给你一个美味程度 $n$ ,请输出这 $10$ 种配料的所有搭配方案。

输入格式

一个正整数 $n$,表示美味程度。

输出格式

第一行,方案总数。

第二行至结束,$10$ 个数,表示每种配料所放的质量,按字典序排列。

如果没有符合要求的方法,就只要在第一行输出一个 $0$。

样例 #1

样例输入 #1

11

样例输出 #1

10
1 1 1 1 1 1 1 1 1 2 
1 1 1 1 1 1 1 1 2 1 
1 1 1 1 1 1 1 2 1 1 
1 1 1 1 1 1 2 1 1 1 
1 1 1 1 1 2 1 1 1 1 
1 1 1 1 2 1 1 1 1 1 
1 1 1 2 1 1 1 1 1 1 
1 1 2 1 1 1 1 1 1 1 
1 2 1 1 1 1 1 1 1 1 
2 1 1 1 1 1 1 1 1 1

提示

对于 $100\%$ 的数据,$n \leq 5000$。

思路

搜索两次,一次输出方案总数,一次输出方案序列。

AC代码

#include <iostream>
#define AUTHOR "HEX9CF"
using namespace std;

int a[15];
int n;
int cnt;
int flg;

void f(int sum, int x, int y)
{
   
    a[y] = x;
    if (10 == y)
    {
   
        if (sum + x == n)
        {
   
            if (flg)
            {
   
                for (int i = 1; i <= 10; i++)
                {
   
                    cout << a[i] << " ";
                }
                cout << endl;
            }
            else
            {
   
                cnt++;
            }
        }
        return;
    }
    for(int i = 1; i <= 3; i++) {
   
        f(sum + x, i, y + 1);
    }
}

int main()
{
   
    cin >> n;
    f(0, 0, 0);
    flg = 1;
    cout << cnt << endl;
    f(0, 0, 0);
    return 0;
}
目录
相关文章
|
缓存
Vue3 详细模板语法及实例
Vue3 详细模板语法及实例
204 0
|
9月前
|
存储 算法 数据挖掘
服务器数据恢复—nas中raid6阵列失效,存储无法访问的数据恢复案例
一台nas上共有14块硬盘组建了一组raid6磁盘阵列。 该nas在工作过程中,raid6阵列中硬盘出现故障离线,导致raid6阵列失效,nas无法正常访问。
|
SQL 关系型数据库 MySQL
MySQL多实例部署:从概念到实操的全面指南
MySQL多实例部署:从概念到实操的全面指南
460 0
|
传感器 监控 安全
物联网通信的基石:LoRa、Sigfox与NB-IoT详解
物联网通信的基石:LoRa、Sigfox与NB-IoT详解
1077 0
|
监控 Java 微服务
使用Spring Boot构建微服务架构
使用Spring Boot构建微服务架构
|
存储
【洛谷 P2437】蜜蜂路线 题解(递归+记忆化搜索+高精度)
蜜蜂路线问题:蜜蜂从蜂房$m$到$n$($m&lt;n$)按数字递增爬行。给定$m$和$n$,求路线数。示例:$m=1$,$n=14$,输出$377$。100%数据$1\leq m,n\leq1000$。使用斐波那契序列优化,高精度处理大数。代码实现斐波那契存储并动态规划求解。
255 0
|
运维 Prometheus 监控
StarRocks 监控报警配置指南
StarRocks 监控报警配置指南
|
人工智能
像相机一样变焦、填充画面细节,还能自定义风格,AI作画神器Midjourney又更新了
像相机一样变焦、填充画面细节,还能自定义风格,AI作画神器Midjourney又更新了
281 1
|
算法
P5019 [NOIP2018 提高组] 铺设道路(贪心算法)
P5019 [NOIP2018 提高组] 铺设道路(贪心算法)
218 0
|
设计模式 uml
设计模式-浅谈依赖倒置原则
设计模式-浅谈依赖倒置原则
191 0