暴力出奇迹 打表出省一
枚举算法
利用计算机运算速度快的特点，对问题的所有可能答案一一列举，并逐一检验，符合条件的保留，不符合的丢弃。
枚举算法简单粗暴，他暴力的枚举所有可能，尽可能地尝试所有的方法。虽然枚举算法非常暴力，而且速度可能很慢，但确实我们最应该优先考虑的！因为枚举法变成实现最简单，并且得到的结果总是正确的。
使用该算法需要满足两个条件:
- 可预先确定候选答案的数量。
- 候选答案的范围在求解之前必须有一个确定的集合。
策略：枚举（穷举）
根据问题的条件将可能的情况一 一列举起来，逐一尝试找出问题的解。有时问题的规模太大，可以排除一些明显不合理的情况。
枚举法的一般规律：
找出枚举范围：分析问题所涉及的所有情况。
找出约束条件：分析问题的解需要满足的条件，并用逻辑表达式解释。
对枚举法的优化主要是对约束范围和约束条件的数学优化。举例：百钱百鸡问题
我国古代数学家张丘建在《算经》一书中提出的数学问题：鸡翁一值钱五，鸡母一值钱三，鸡雏三值钱一。百钱买百鸡，问鸡翁、鸡母、鸡雏各几何？
分析：
隐含约束条件：Z%3 = 0，因为鸡肯定是整只的（肯德鸡除外）。所以鸡仔的个数是3的倍数。
算法：注意：计算机中遇到除法要小心！
#include <iostream>
int main()
{
int x,y,z;
int count = 0;
for(x=0;x<=100;x++){
for(y=0;y<=100;y++){
for(z=0;z<=100;z++){
count++; //计算穷举次数
if (z%3==0 &&x*5+y*3+z/3==100&&x+y+z == 100)
std::cout<<"公鸡: "<<x<<" 母鸡: "<< y << " 小鸡: "<<z<<std::endl;
}
}
}
std::cout << count;
return 0;
}
这个方法三层for循环，的算法复杂度是0（n^3），穷举次数是100万级别，简直不能忍
数学初步优化
再考虑一下题设条件：全部钱买公鸡可以买100/5 = 20；全部钱买母鸡可以买约33个，而鸡仔是100 -（X+Y）
则约束条件为：0<= X<=20；0<=y<=33；Z = 100 -（X+Y）；Z%3=0；
#include <iostream>
int main()
{
int x,y,z;
int count = 0;
for(x=0;x<=20;x++){
for(y=0;y<=33;y++){
count++;
z=100-x-y;
if (z%3==0 &&x*5+y*3+z/3==100)
std::cout<<"公鸡: "<<x<<" 母鸡: "<< y << " 小鸡: "<<z<<std::endl;
}
}
std::cout << count;
return 0;
}
枚举714次。对比第一个简直快了99/100。两层for循环，算法复杂度是O(n^2)
数学进一步优化 在 2）中的约束条件：0<= X<=20；0<= Y<=33；Z = 100 -（X+Y）；Z%3=0;
由 X+Y+Z = 100和5X + 3Y + Z/3 = 100可得7X+4Y=100
则Y = 25 – （7/4）X
再令X = 4K，则有Y = 25 – 7K，继而Z = 75 + 3K
因为 0=< Z <=100，所以K的可能取值是0，1，2，3
#include<iostream>
int main()
{
int x,y,z;
int count = 0;
for (int k = 0; k <= 3; k++){
count ++;
x = 4 * k;
y = 25 - 7 * k;
z = 75 + 3 * k;
std::cout<<"公鸡: "<<x<<" 母鸡: "<< y << " 小鸡: "<<z<<std::endl;
}
std::cout << count;
return 0;
}
一个for循环，可在常数时间内算出。
实例讲解
P2241 统计方形(数据加强版)
分析
矩形长为a, 宽为b, 这样的矩形的个数是 (n-a+1) * (m-b+1). 枚举所有a和b的可能情况就可以算出矩形的个数. 如果a == b, 则为正方形, 反之为长方形.
参考代码:
#include <iostream>
using namespace std;
long long n, m, ans1, ans2;
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++) {
if(i == j)
ans1 += (n - i + 1) * (m - j + 1);
else
ans2 += (n - i + 1) * (m - j + 1);
}
cout << ans1 << " " << ans2;
return 0;
}
P2089 烤鸡
分析
10种配料, 每种1-3克. 求所有的搭配方案. 答案的范围是固定的. 就是每种配料的1-3克的组合. 枚举每种每种组合, 如果这种组合下, 配料总质量为所要求的,就保留这个答案.
#include <cstdio>
using namespace std;
int n,i;
int a[10000000][10];
int main()
{
scanf("%d", &n);
if (n > 30 || n < 10) {
printf("0");
return 0;
}
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)
{
a[i][0]=a1;
a[i][1]=a2;
a[i][2]=a3;
a[i][3]=a4;
a[i][4]=a5;
a[i][5]=a6;
a[i][6]=a7;
a[i][7]=a8;
a[i][8]=a9;
a[i][9]=a10;
i++;
}
}
}
}
}
}
}
}
}
}
}
printf("%d\n", i);
for(int k=0; k <i; k++) {
for(int j=0; j < 10; j++) {
printf("%d ", a[k][j]);
}
printf("\n");
}
return 0;
}P1149 火柴棒等式
分析
数据的范围是n <= 24, 数据很小. 可以枚举出 24个火柴所能组成的数的范围, 然后枚举这些数中符合等式且火柴数量符合要求的答案.
参考代码
#include <cstdio>
using namespace std;
#define MAX 20000
int a[MAX]= {6, 2, 5, 5, 4, 5, 6, 3, 7, 6,};
int n, cnt = 0;
int main()
{
scanf("%d", &n);
for(int i = 10; i < MAX; i++){
a[i] = 0;
int k = i;
while(k) {
a[i] += a[k%10];
k/=10;
}
//printf("a[%d]= %d\n", i, a[i]);
}
for(int i = 0; i < MAX/2; i++) {
for(int j=0; j < MAX/2; j++) {
if(a[i] + a[j] + a[i+j] + 4 == n) {
cnt++;
//printf("%d: %d + %d = %d\n", cnt, i , j , i+j);
}
}
}
printf("%d", cnt);
}题单:
- P2241 统计方形（数据加强版）
- P2089 烤鸡
- P1618 三连击（升级版）
- P1036 选数
- P1157 组合的输出
- P1706 全排列问题
- P1088 火星人
- P3392 涂国旗
- P3654 First Step (ファーストステップ)
- P1217 [USACO1.5]回文质数 Prime Palindromes
- P1149 火柴棒等式
- P3799 妖梦拼木棒
- P2392 kkksc03考前临时抱佛脚
- P2036 [COCI2008-2009#2] PERKET