P2089 烤鸡 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
之前的dp系列太伤作者的心了,还是暴力系列最抚人心。
咳咳咳,虽然本题可以直接10层for循环暴力枚举,但那样太不优雅了,要优雅嘛。
所以直接上dfs,dfs永远的神。
本题要求先输出方案数量在输出具体方案。
我们使用字符串来记录具体方案答案,开个ArrayList来记录答案数量。
具体看注释,代码和注释相结合
java">import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
int a=Integer.parseInt(br.readLine());
aa=a;
int b=10;
if(a<10||a>30){//判断如果美味值超过我们的上限和下限那么直接输出0
System.out.println("0");
return;
}
dfs(0,"",0);//开始跑dfs
System.out.println(al.size());
for(String e:al){
System.out.println(e);//输出答案
}
}
public static ArrayList<String> al=new ArrayList<>();
public static int aa;
public static void dfs(int a,String b,int c){
if(c>aa){//如果美味值超出要求结束搜索
return;//其实为了节约时间还可以判断当前的调料种类数超过10种直接结束的.
}
if(a==10&&c==aa){//当我们的每种调料都使用过了并且达到美味值,我们储存答案。
al.add(b);
return;
}
for(int d=1;d<=3;d++){//遍历搜索
dfs(a+1,b+d+" ",c+d);
}
}
}