题目背景
猪猪 Hanke 得到了一只鸡。
题目描述
猪猪 Hanke 特别喜欢吃烤鸡(本是同畜牲,相煎何太急!)Hanke 吃鸡很特别,为什么特别呢?因为他有 1010 种配料(芥末、孜然等),每种配料可以放 11 到 33 克,任意烤鸡的美味程度为所有配料质量之和。
现在, Hanke 想要知道,如果给你一个美味程度 nn ,请输出这 1010 种配料的所有搭配方案。
输入格式
一个正整数 nn,表示美味程度。
输出格式
第一行,方案总数。
第二行至结束,1010 个数,表示每种配料所放的质量,按字典序排列。
如果没有符合要求的方法,就只要在第一行输出一个 00。
输入输出样例
输入 #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% 的数据,n \leq 5000n≤5000。
暴力枚举:
#include<stdio.h>
int a[100000][11],n,cnt;
int main(){
scanf("%d",&n);
if(n<10&&n>30){
printf("0\n");
}else {
for(int i=1;i<=3;i++){
for(int j=1;j<=3;j++){
for(int k=1;k<=3;k++){
for(int i4=1;i4<=3;i4++){
for(int i5=1;i5<=3;i5++){
for(int i6=1;i6<=3;i6++){
for(int i7=1;i7<=3;i7++){
for(int i8=1;i8<=3;i8++){
for(int i9=1;i9<=3;i9++){
for(int i0=1;i0<=3;i0++){
if(i+j+k+i4+i5+i6+i7+i8+i9+i0==n){
a[cnt][0]=i;
a[cnt][1]=j;
a[cnt][2]=k;
a[cnt][3]=i4;
a[cnt][4]=i5;
a[cnt][5]=i6;
a[cnt][6]=i7;
a[cnt][7]=i8;
a[cnt][8]=i9;
a[cnt][9]=i0;
cnt++;
}
}
}
}
}
}
}
}
}
}
}
}
printf("%d\n",cnt);
for(int i=0;i<cnt;i++){
for(int j=0;j<10;j++){
printf("%d ",a[i][j]);
}
puts("");
}
return 0;
}
深搜(回溯):
#include<iostream>
using namespace std;
int a[10000][11], cnt, local_n, n, b[11];
//以当前位置为基准,处理当前情况
void dfs(int t, int local_n) {
if (local_n == n && t > 10) {//必须要>10,不能>=,t=11时,搜索到此处实际仅有十次,因为判断条件总是在主体代码前
cnt++;
for (int i = 1; i <= 10; i++) {
a[cnt][i] = b[i];
}
}
if(t>10) return ;
for (int j = 1; j <= 3; j++) {//对当前情况进行处理
if (local_n + j > n) break;
b[t] = j;
dfs(t + 1, local_n + j);
b[t] = 0;
}
}
int main() {
cin >> n;
dfs(1, 0);
cout << cnt << endl;
for (int i = 1; i <= cnt; i++) {
for (int j = 1; j <= 10; j++) {
cout << a[i][j] << ' ';
}
puts("");
}
return 0;
}