題目背景
豬豬 Hanke 得到了一只雞。
題目描述
豬豬 Hanke 特別喜歡吃烤雞（本是同畜牲，相煎何太急?。〩anke 吃雞很特別，為什么特別呢？因?yàn)樗?10 種配料（芥末、孜然等），每種配料可以放 1 到 3 克，任意烤雞的美味程度為所有配料質(zhì)量之和。
現(xiàn)在， Hanke 想要知道，如果給你一個(gè)美味程度 n ，請(qǐng)輸出這 10 種配料的所有搭配方案。
輸入格式
一個(gè)正整數(shù) n，表示美味程度。
輸出格式
第一行，方案總數(shù)。
第二行至結(jié)束，10 個(gè)數(shù)，表示每種配料所放的質(zhì)量，按字典序排列。
如果沒(méi)有符合要求的方法，就只要在第一行輸出一個(gè) 0。
輸入輸出樣例
輸入 #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
說(shuō)明/提示
對(duì)于 100% 的數(shù)據(jù)，n≤5000。
方法一
暴力破解
import java.util.Scanner;
public class 烤雞 {
public static void main(String[]args) {
? Scanner sc=new Scanner(System.in);
? int n=sc.nextInt();
? int a,b,c,d,e,f,g,h,i,j,count = 0;
? for(a=1;a<=3;a++) {
? for(b=1;b<=3;b++) {
? ? for(c=1;c<=3;c++) {
? ? for(d=1;d<=3;d++) {
? ? ? for(e=1;e<=3;e++) {
? ? ? for(f=1;f<=3;f++) {
? ? ? ? for(g=1;g<=3;g++) {
? ? ? ? for(h=1;h<=3;h++) {
? ? ? ? ? for(i=1;i<=3;i++) {
? ? ? ? ? for(j=1;j<=3;j++) {
? ? ? ? ? ? if(a+b+c+d+e+f+g+h+i+j==n) {
? ? ? ? ? ? count++;
? ? ? ? ? ? }
? ? ? ? ? }
? ? ? ? ? }
? ? ? ? }
? ? ? ? }
? ? ? }
? ? ? }
? ? }
? ? }
? }
? }
? System.out.println(count);
? for(a=1;a<=3;a++) {
? for(b=1;b<=3;b++) {
? ? for(c=1;c<=3;c++) {
? ? for(d=1;d<=3;d++) {
? ? ? for(e=1;e<=3;e++) {
? ? ? for(f=1;f<=3;f++) {
? ? ? ? for(g=1;g<=3;g++) {
? ? ? ? for(h=1;h<=3;h++) {
? ? ? ? ? for(i=1;i<=3;i++) {
? ? ? ? ? for(j=1;j<=3;j++) {
? ? ? ? ? ? if(a+b+c+d+e+f+g+h+i+j==n) {
System.out.println(a+" "+b+" "+c+" "+d+" "+e+" "+f+" "+g+" "+h+" "+i+" "+j);
? ? ? ? ? ? }
? ? ? ? ? }
? ? ? ? ? }
? ? ? ? }
? ? ? ? }
? ? ? }
? ? ? }
? ? }
? ? }
? }
? }
}
}
方法二
dfs
此題需要先輸出方案，故每個(gè)方案需要保存在一個(gè)ans數(shù)組中；一維為第幾種方案，二維為方案內(nèi)容；
在dfs中，兩個(gè)參數(shù)，層數(shù)u，目前的調(diào)料質(zhì)量之和sum；
這種方法我目前還沒(méi)學(xué)到，先收藏起來(lái)，以后再分析
import java.util.Scanner;
public class Main {
? ? static int n;
? ? static int[][] ans = new int[100000][15];//一維為第幾種方案，二維為方案內(nèi)容
? ? static int[] temp = new int[15];//保存臨時(shí)方案
? ? static int cnt = 0;//方案總數(shù)
? ? static void dfs(int u, int sum) {
? ? ? ? if (u == 10) {//搜索到底，滿足輸出條件，保存方案
? ? ? ? ? ? if (sum == n) {
? ? ? ? ? ? ? ? for (int i = 0; i < 10; i++)
? ? ? ? ? ? ? ? ? ? ans[cnt][i] = temp[i];
? ? ? ? ? ? ? ? cnt++;
? ? ? ? ? ? }
? ? ? ? ? ? return;//搜索到底，回溯
? ? ? ? }
? ? ? ? for (int i = 1; i <= 3; i++) {//每一層可選的
? ? ? ? ? ? temp[u] = i;//當(dāng)前的調(diào)料放的量
? ? ? ? ? ? dfs(u + 1, sum + i);
? ? ? ? ? ? temp[u]=0;
? ? ? ? }
? ? }
? ? public static void main(String[] args) {
? ? ? ? Scanner sc = new Scanner(System.in);
? ? ? ? n = sc.nextInt();
? ? ? ? dfs(0, 0);//從第一層搜起,質(zhì)量和為0
? ? ? ? System.out.println(cnt);
? ? ? ? if (cnt != 0)
? ? ? ? ? ? for (int i = 0; i < cnt; i++) {
? ? ? ? ? ? ? ? for (int j = 0; j < 10; j++)
? ? ? ? ? ? ? ? ? ? System.out.print(ans[i][j]+" ");
? ? ? ? ? ? ? ? System.out.println();
? ? ? ? ? ? }
? ? }
}
