P2089烤鸡

P2089烤鸡

题目背景

猪猪 Hanke 得到了一只鸡。

题目描述

猪猪 Hanke 特别喜欢吃烤鸡（本是同畜牲，相煎何太急！）Hanke 吃鸡很特别，为什么特别呢？因为他有 1010 种配料（芥末、孜然等），每种配料可以放 11 到 33 克，任意烤鸡的美味程度为所有配料质量之和。

现在， Hanke 想要知道，如果给你一个美味程度 nn ，请输出这 1010 种配料的所有搭配方案。

输入格式

一个正整数 nn，表示美味程度。

输出格式

第一行，方案总数。

第二行至结束，1010 个数，表示每种配料所放的质量，按字典序排列。

如果没有符合要求的方法，就只要在第一行输出一个 00。

输入输出样例

输入 #1复制

11

输出 #1复制

10
1 1 1 1 1 1 1 1 1 2 
1 1 1 1 1 1 1 1 2 1 
1 1 1 1 1 1 1 2 1 1 
1 1 1 1 1 1 2 1 1 1 
1 1 1 1 1 2 1 1 1 1 
1 1 1 1 2 1 1 1 1 1 
1 1 1 2 1 1 1 1 1 1 
1 1 2 1 1 1 1 1 1 1 
1 2 1 1 1 1 1 1 1 1 
2 1 1 1 1 1 1 1 1 1 

说明/提示

对于 100%100% 的数据，n leq 5000n≤5000。

做法一：暴力枚举时间复杂度3^10

#include<bits/stdc++.h>
using namespace std;
int main(){int n , ans = 0;cin >> n;for(int a1 = 1 ; a1 <= 3 ; a1++)for(int a2 = 1 ; a2 <= 3 ; a2++)for(int a3 = 1 ; a3 <= 3 ; a3++)for(int a4 = 1 ; a4 <= 3 ; a4++)for(int a5 = 1 ; a5 <= 3 ; a5++)for(int a6 = 1 ; a6 <= 3 ; a6++)for(int a7 = 1 ; a7 <= 3 ; a7++)for(int a8 = 1 ; a8 <= 3 ; a8++)for(int a9 = 1 ; a9 <= 3 ; a9++)for(int a10 = 1 ; a10 <= 3 ; a10++)if(a1 + a2 + a3 + a4 + a5 + a6 + a7 + a8 + a9 + a10 == n) ans++;cout << ans << endl;for(int a1 = 1 ; a1 <= 3 ; a1++)for(int a2 = 1 ; a2 <= 3 ; a2++)for(int a3 = 1 ; a3 <= 3 ; a3++)for(int a4 = 1 ; a4 <= 3 ; a4++)for(int a5 = 1 ; a5 <= 3 ; a5++)for(int a6 = 1 ; a6 <= 3 ; a6++)for(int a7 = 1 ; a7 <= 3 ; a7++)for(int a8 = 1 ; a8 <= 3 ; a8++)for(int a9 = 1 ; a9 <= 3 ; a9++)for(int a10 = 1 ; a10 <= 3 ; a10++)if(a1 + a2 + a3 + a4 + a5 + a6 + a7 + a8 + a9 + a10 == n)printf("%d %d %d %d %d %d %d %d %d %dn" , a1 , a2 , a3 , a4 , a5 , a6 , a7 , a8 , a9 , a10);return 0;
}

做法二：剪枝做法

#include<bits/stdc++.h>
using namespace std;
#define f(i , a , b) for(int i = max(1 , a) ; i <= min(3 , b) ; i++)
int main(){int n , arr[100][10] , ans = 0;scanf("%d" , &n);f(a1 , n - 27 , n - 9)f(a2 , n - 24 - a1 , n - 8 - a1)f(a3 , n - 21 - a1 - a2 , n - 7 - a1 - a2)f(a4 , n - 18 - a1 - a2 - a3 , n - 6 - a1 - a2 - a3)f(a5 , n - 15 - a1 - a2 - a3 - a4 , n - 5 - a1 - a2 - a3 - a4)f(a6 , n - 12 - a1 - a2 - a3 - a4 - a5 , n - 4 - a1 - a2 - a3 - a4 - a5)f(a7 , n - 9 - a1 - a2 - a3 - a4 - a5 - a6 , n - 3 - a1 - a2 - a3 - a4 - a5 - a6)f(a8 , n - 6 - a1 - a2 - a3 - a4 - a5 - a6 - a7 , n - 2 - a1 - a2 - a3 - a4 - a5 - a6 - a7)f(a9 , n - 3 - a1 - a2 - a3 - a4 - a5 - a6 - a7 - a8 , n - 1 - a1 - a2 - a3 - a4 - a5 - a6 - a7 - a8)f(a10 , n - a1 - a2 - a3 - a4 - a5 - a6 - a7 - a8 - a9 , n - a1 - a2 - a3 - a4 - a5 - a6 - a7 - a8 - a9){ arr[ans][0] = a1 ; arr[ans][1] = a2 ; arr[ans][2] = a3 ; arr[ans][3] = a4 ; arr[ans][4] = a5 ; arr[ans][5] = a6 ; arr[ans][6] = a7 ; arr[ans][7] = a8 ; arr[ans][8] = a9 ; arr[ans][9] = a10 ; ans++;}cout << ans << endl;for(int i = 0 ; i < ans ; i++){for(int j = 0; j < 10 ; j++){cout << arr[i][j] << " ";}cout << endl;}return 0;
}

做法三：打表法

小贴士：打表法 称为打表法，是一种常用竞赛技巧。 优点：可以完全忽略时间限制。 缺点：受空间限制和代码长度限制；当输入规模较大时无法使用。 适用情况： • 赛场上无法写出正解，可使用此法获取部分分。 • 可以手工预处理小数据，减少暴力枚举规模。 • 从小数据中发现规律，从而做出正解。 • 提交答案题