P2089 烤鸡——题解

解题思路

从第一种配料开始 DFS，每层尝试 $1,2,3$。可根据剩余配料最小和最大可能贡献进行剪枝：若当前和即使全取 1 也超过目标，或全取 3 仍达不到目标，就不再递归。按 $1,2,3$ 尝试保证字典序。

复杂度分析

最多枚举 $3^{10}=59049$ 个叶子，时间复杂度 $O(3^{10})$，空间复杂度 $O(10)$（不计输出保存）。

C++17 参考代码

#include <bits/stdc++.h>
using namespace std;
int n,a[11]; vector<array<int,10>> ans;
void dfs(int dep,int sum){
    if(dep==10){
        if(sum==n){array<int,10> v;for(int i=0;i<10;i++)v[i]=a[i];ans.push_back(v);}return;
    }
    int left=9-dep;
    for(int x=1;x<=3;x++){
        int ns=sum+x;
        if(ns+left<=n&&ns+3*left>=n){a[dep]=x;dfs(dep+1,ns);}
    }
}
int main(){
    cin>>n;
    if(n>=10&&n<=30) dfs(0,0);
    cout<<ans.size()<<'\n';
    for(auto &v:ans){for(int i=0;i<10;i++){if(i)cout<<' ';cout<<v[i];}cout<<'\n';}
    return 0;
}

#include <bits/stdc++.h> using namespace std; int n,a[11]; vector<array<int,10>> ans; void dfs(int dep,int sum){ if(dep10){ if(sumn){array<int,10> v;for(int i=0;i<10;i++)v[i]=a[i];ans.push_back(v);}return; } int left=9-dep; for(int x=1;x<=3;x++){ int ns=sum+x; if(ns+left<=n&&ns+3*left>=n){a[dep]=x;dfs(dep+1,ns);} } } int main(){ cin>>n; if(n>=10&&n<=30) dfs(0,0); cout<<ans.size()<<'\n'; for(auto &v:ans){for(int i=0;i<10;i++){if(i)cout<<' ';cout<<v[i];}cout<<'\n';} return 0; }