P2089 烤鸡----题解
p2089烤鸡
题意：
本是同畜牲，相煎何太疾！
Hanke 吃鸡很特别，为什么特别呢？因为他有10 种配料（芥末、孜然等），每种配料可以放 1到3 克，任意烤鸡的美味程度为所有配料质量之和。现在， Hanke 想要知道，如果给你一个美味程度 n ，请输出这 10 种配料的所有搭配方案。
思路：
正解是爆搜，歪解是枚举。
为了方便c++初学者能够不被棕名的AC1道橙题，先给出暴力枚举代码
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,sum=0;//sum是方案总数
cin>>n;
for(int i1=1;i1<=3;i1++)
{
for(int i2=1;i2<=3;i2++)
{
for(int i3=1;i3<=3;i3++)
{
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 i10=1;i10<=3;i10++)
{
if(i1+i2+i3+i4+i5+i6+i7+i8+i9+i10==n)//美味程度是n
{
sum++;//方案数sum+1
}
}
}
}
}
}
}
}
}
}
}
cout<<sum<<endl;
for(int i1=1;i1<=3;i1++)
{
for(int i2=1;i2<=3;i2++)
{
for(int i3=1;i3<=3;i3++)
{
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 i10=1;i10<=3;i10++)
{
if(i1+i2+i3+i4+i5+i6+i7+i8+i9+i10==n)
{
cout<<i1<<" "<<i2<<" "<<i3<<" "<<i4<<" "<<i5<<" "<<i6<<" "<<i7<<" "<<i8<<" "<<i9<<" "<<i10<<" "<<endl;//输出搭配方案
}
}
}
}
}
}
}
}
}
}
}
return 0;
}让我们回到爆搜
其实这题跟p2386放苹果有点像，也是1个一个的把配料放入烤鸡中。
不过要注意，题目让我们既输出方案数，也输出请输出这 10 种配料的所有搭配方案。我们不能边输出方案数便输出搭配方案。
所有我们要定义变量flag,如果flag=0，输出方案数，如果flag=1,输出这 10 种配料的所有搭配方案
代码：
#include<bits/stdc++.h>
using namespace std;
int ans[1000005],sum=0,total=0;
bool flag=0;
int n;
void dfs(int x)//x是配料放的数量
{
if(x>10)//如果配料数量放完了。
{
if(sum==n)//如果美味程度是n
{
total++;//方案数+1
if(flag==1)//如果要输出搭配方案
{
for(int i=1;i<=10;i++) cout<<ans[i]<<" ";//输出10种配料的搭配方案
cout<<endl;//换行
}
}
return ;//返回
}
for(int i=1;i<=3;i++)//使用for循环放配料
{
ans[x]=i;//第x种配料放i克
sum+=i;//美味程度又多了i
dfs(x+1);//放下一个配料
ans[x]=0;//下一个配料还没有放
sum-=i;//美味程度又减少了i，注意，这是下一个配料的美味程度。
}
}
int main()
{
cin>>n;//输入
dfs(1);//调用自定义深搜函数dfs
cout<<total<<endl;//输出方案数
flag=1;//如果flag=1，就要输出搭配方案了
dfs(1);//再次搜索，太暴力了。
return 0;//考场不写，泪流满面！
}