63 lines
3.1 KiB
C++
63 lines
3.1 KiB
C++
#include <bits/stdc++.h>
|
||
|
||
using namespace std;
|
||
const int N = 100010;
|
||
//方案数量，预计,注意，此处可不是n的数据上限，而是可能的方案数量，尽量开大防止出错，黄海就因为开小了挂掉！
|
||
const int M = 20; //配料的数量，本题目是10，为了开大一点数组，加了10
|
||
|
||
int a[N][M]; //保存所有可行的方案,描述，第i种方案，放过二维的第一个格子0，第二个格子1表示i种方案中第一个配料用多少克
|
||
int path[M]; //记录当前正在计算的方案.本题经验，数组开小了，会出错n值错乱的诡异问题！！！！描述当前方案每一种配料用多少克
|
||
/**
|
||
C++语言中数组越界访问系统不会给出任何的提示，程序员可以超出数组边界进行读/写从而造成内存的混乱，
|
||
而这种错误对初学者来说是很容易出现的、而又偏偏是很难调试的，因为系统不会给出错误的提示，所以就这样使用数组是不安全的。
|
||
*/
|
||
|
||
/**
|
||
对比暴力无脑大模拟，dfs的使用范围更广，很好理解，比如我们不知道要多少轮，轮次数需要输入进来，我们就没有办法预先控制循环的层数，
|
||
而dfs天生就是可以处理不定层数的！
|
||
*/
|
||
int n, cnt; //美味值，可行方案数量
|
||
|
||
/**
|
||
* 假设我们在面临一种通用的场景，也就是通常说的“一般性场景”
|
||
* (1)我们正在准备放入第step件调料，目前的情况是没放此种调料之前的美味值是sum
|
||
* (2)第step件调料，我们可以选择放入1，2，3三种数量，需要用循环把这些都尝试一遍。
|
||
* (3)如果我们选择完了数量i之后，我们需要继续向下一种调料出发，但情况已经发生了变化，变成处理第
|
||
* step+1件调料，同时总和也变成了sum+i
|
||
* (4)当处理完第10件调料后，也就是step=9(因为step是从0开始的)时，再向下就是递归出口，在这里判断是不是一组可行解。
|
||
*/
|
||
//step为第几种调料，sum目前的配料之和
|
||
void dfs(int step, int sum) {
|
||
if (step == 11) { //当10种调料都分析完了
|
||
//如果配料之和等于输入值;
|
||
//使用memcpy更简单,参数：目标数组，源数组，长度
|
||
if (sum == n)memcpy(a[cnt++], path, sizeof path);
|
||
//不管等不等，都需要返回了，递归的出口
|
||
return;
|
||
}
|
||
//在当前step下，就是在讨论某一种调料时，面临三种选择，1，2，3
|
||
for (int i = 1; i <= 3; i++) {
|
||
path[step] = i; //第step种调料的配料为i
|
||
dfs(step + 1, sum + i); //递归，对下一种调料做同样的分析
|
||
}
|
||
}
|
||
|
||
|
||
int main() {
|
||
cin >> n;
|
||
|
||
//从第1步开始，目前总和是0
|
||
dfs(1, 0);
|
||
|
||
//输出方案个数
|
||
cout << cnt << endl;
|
||
//再输出具体的方案
|
||
if (cnt > 0) {
|
||
for (int i = 0; i < cnt; i++) {
|
||
for (int j = 1; j <= 10; j++)
|
||
cout << a[i][j] << " ";
|
||
cout << endl;
|
||
}
|
||
}
|
||
return 0;
|
||
} |