烤鸡
题目 烤鸡
思路分析
首先朴素做法就是 每一种调料对应每一位 每位都有1 2 3 三种选法
某种方案达到10的时候 说明10种调料都选择完毕了 结束本次递归
#include<bits/stdc++.h>
using namespace std;
const int N=20;
int plans[N]; //1表示放一克 2表示放两克 3表示放三克
int n;
int res;
vector<vector<int>> ans;
void dfs(int u){
if(u>10){
int sum=0;
for(int i=1;i<=10;i++)
sum+=plans[i];
if(sum==n){
ans.push_back(vector<int>(plans + 1, plans + 11));
res++;
}
return;
}
plans[u]=1;
dfs(u+1);
plans[u]=0;
plans[u]=2;
dfs(u+1);
plans[u]=0;
plans[u]=3;
dfs(u+1);
plans[u]=0;
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n;
dfs(1);
cout<<res<<endl;
for(auto plan:ans) {
for(int i=0;i<10;i++) {
cout<<plan[i]<<" ";
}
cout<<endl;
}
return 0;
}
这是没有考虑任何优化的 甚至1，2，3三种选择都分开写了
也能ac
考虑一下优化 若某种方案在选到最后一位之前 就已经超过n了 就说明这种方案肯定不行 所以这个枝是可以剪去的 不妨把当前的sum也作为一个参数传入 方便剪枝
#include<bits/stdc++.h>
using namespace std;
const int N=20;
int plans[N]; //1表示放一克 2表示放两克 3表示放三克
int n;
int res;
vector<vector<int>> ans;
void dfs(int u,int sum){
if(sum>n) return;
if(u>10){
if(sum==n){
ans.push_back(vector<int>(plans + 1, plans + 11));
res++;
}
return;
}
for(int i=1;i<=3;i++){
plans[u]=i;
dfs(u+1,sum+i);
plans[u]=0;
}
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n;
dfs(1,0);
cout<<res<<endl;
for(auto plan:ans) {
for(int i=0;i<10;i++) {
cout<<plan[i]<<" ";
}
cout<<endl;
}
return 0;
}
代码实现
不剪枝
#include<bits/stdc++.h>
using namespace std;
const int N=5010;
int path[N];
int n,res;
vector<vector<int>> ans;
void dfs(int u){
if(u>10){
int sum=0;
for(int i=1;i<=10;i++){
sum+=path[i];
}
if(sum==n){
res++;
ans.push_back(vector<int>(path+1,path+10+1));
}
return;
}
for(int i=1;i<=3;i++){
path[u]=i;
dfs(u+1);
path[u]=0;
}
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n;
dfs(1);
cout<<res<<endl;
if(res){
for(auto plan:ans){
for(int i=0;i<10;i++){
cout<<plan[i]<<" ";
}
cout<<endl;
}
}
return 0;
}
剪枝
#include<bits/stdc++.h>
using namespace std;
const int N=5010;
int path[N];
int n,res;
vector<vector<int>> ans;
void dfs(int u,int sum){
if(sum>n)
return;
if(u>10){
if(sum==n){
res++;
ans.push_back(vector<int>(path+1,path+10+1));
}
return;
}
for(int i=1;i<=3;i++){
path[u]=i;
dfs(u+1,sum+i);
path[u]=0;
}
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n;
dfs(1,0);
cout<<res<<endl;
if(res){
for(auto plan:ans){
for(int i=0;i<10;i++){
cout<<plan[i]<<" ";
}
cout<<endl;
}
}
return 0;
}
💬 评论