洛谷 P2089 烤鸡

时间:2021-05-23 06:43:35

看了前面大佬的代码,发现这道题的解题思路都大同小异。

首先肯定要定义一个变量累加方案数量,因为方案数量要最先输出,所以所有方案要先储存下来。个人不喜欢太多数组,就只定义一个字符串。

然后我们发现只有10种配料,每中在1~3以内,我们便可以模拟一下四进制(4^9==262144,在int范围内)。

## 累加函数:
```cpp
string tot;int n,m;//预备工作

void leiji(int a){//进行累加的函数
int b=262144;//模拟四进制
while(a){
tot+=a/b+'0';//用短除法得出各个位上的数。(要倒着来 )
tot+=' ';//这个空格很重要!
a%=b;b/=4;
}
tot+='\n';m++;//换行符也很重要!(m是方案数量)
}
## 递归函数:cpp
void f(int s,int k){
if(s<1&&k<262145)return;//美味程度达到了 配料还有剩
if(s>0&&k>262144)return;//配料放完了而美味程度没达到
if(s==0&&k>262144){//达到要求
leiji(k);
return;
}//以上三种为递归边界
f(s-1,k4+1);
f(s-2,k
4+2);//k4是模拟四进制
f(s-3,k
4+3);
}
## 主函数:cpp
int main(){//主函数
cin>>n;
f(n,0);
cout<<m<<endl<<tot;//输出,圆满
return 0;
}
```