江苏省住房和城乡建设局网站,河北邯郸封闭最新消息,高端建站是什么,seo服务如何收费#x1f61a;一个不甘平凡的普通人#xff0c;日更算法学习和打卡#xff0c;期待您的关注和认可#xff0c;陪您一起学习打卡#xff01;#xff01;#xff01;#x1f618;#x1f618;#x1f618; #x1f917;专栏#xff1a;每日算法学习 #x1f4ac;个人… 一个不甘平凡的普通人日更算法学习和打卡期待您的关注和认可陪您一起学习打卡 专栏每日算法学习 个人主页个人主页 算法分类dfs练习 语言java 题目来源洛谷 P2089 烤鸡
文章目录烤鸡题目背景题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1提示思路完整代码结果烤鸡
题目背景
猪猪 Hanke 得到了一只鸡。
题目描述
猪猪 Hanke 特别喜欢吃烤鸡本是同畜牲相煎何太急Hanke 吃鸡很特别为什么特别呢因为他有 101010 种配料芥末、孜然等每种配料可以放 111 到 333 克任意烤鸡的美味程度为所有配料质量之和。
现在 Hanke 想要知道如果给你一个美味程度 nnn 请输出这 101010 种配料的所有搭配方案。
输入格式
一个正整数 nnn表示美味程度。
输出格式
第一行方案总数。
第二行至结束101010 个数表示每种配料所放的质量按字典序排列。
如果没有符合要求的方法就只要在第一行输出一个 000。
样例 #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%100\%100% 的数据n≤5000n \leq 5000n≤5000。
思路
每种佐料有三种情况所以总的情况不会超过3^10我们枚举每一种情况定义一个数组来每种方案内佐料的质量定义一个sum来统计总重作为回溯的条件最后输出即可。
完整代码
import java.util.Scanner;public class Main {//方案数static int res;//存储static int count;static int arr[];static int hello[][] new int [59050][11];static int N;public static void main(String[] args) {Scanner s new Scanner(System.in);N s.nextInt();arr new int [20];dfs(1,0);System.out.println(res);for(int i 1;ires;i) {for(int j 1;j10;j) {System.out.print(hello[i][j] );}System.out.println();}}public static void dfs(int index,int sum) {if(sumN) return;if(index10) {if(sum N) {res;for(int i1;i10;i) {hello[res][i] arr[i];}}return ;}for(int i 1;i3;i) {arr[index] i;dfs(index1, sumi);arr[index] 0;}}
}结果 感谢您的阅读希望对您有所帮助。关注我完成每日算法自律打卡什么时候开始都不晚
