枚举
枚举是基于逐个尝试答案的一种问题求解策略。
基本思想：
- 建立简洁的数学模型
- 减小搜索空间
- 采用合理的搜索顺序
枚举算法是利用计算机快速的处理能力，对某一问题的每一种可能的解进行遍历、查找的方法。枚举算法实现起来相对简单，代码量短，并且容易理解，是相对基础的一种算法。
实现枚举算时有两点需要注意：一是要保证枚举了每一种情况，不会有遗漏的情形发生，这是枚举算法正确性的保证；二是在枚举时要保证每种情形只枚举一次，尽量避免重复的计算，这样才能保证时间复杂度在可以接受范围内。
同时，对于实际问题，也要学会分析枚举算法的效率，并对具体的算法进行一定的优化，尽可能地减少不必要的计算。例如，当前枚举的所有情况中的最好结果都不可能比已有结果更优时就可以直接退出。类似这样的优化还有很多。
总而言之，对于一个问题，如果没有很好的求解方法，那么不妨尝试枚举算法。
例如：求小于N的最大素数
-找不到一个数学公式，使得根据N就可以计算出这个素数
-N-1是素数吗？N-2是素数吗？
-判断N-i是否是素数的问题
-转化为求小于N的全部素数（可以用筛法）
例题1：完美立方
形如a3= b3 + c3 + d3的等式被称为完美立方等式。例如123= 63 + 83 + 103 。编写一个程序，对任给的正整数N (N≤100)，寻找所有的四元组(a, b, c, d)，使得a3 = b3 + c3 + d3，其中a,b,c,d 大于 1, 小于等于N，且b<=c<=d。
输入
一个正整数N (N≤100)。
输出
每行输出一个完美立方。输出格式为：
Cube = a, Triple = (b,c,d)
其中a,b,c,d所在位置分别用实际求出四元组值代入。
请按照a的值，从小到大依次输出。当两个完美立方等式中a的值相同，则b值小的优先输出、仍相同则c值小的优先输出、再相同则d值小的先输出。
样例输入
24
样例输出
Cube = 6, Triple = (3,4,5)
Cube = 12, Triple = (6,8,10)
Cube = 18, Triple = (2,12,16)
Cube = 18, Triple = (9,12,15)
Cube = 19, Triple = (3,10,18)
Cube = 20, Triple = (7,14,17)
Cube = 24, Triple = (12,16,20)
解题思路：
四重循环枚举a,b,c,d,a在最外层，d在最里层，每一层都是从小到大枚举，
a的枚举范围[2,N]
b的枚举范围[2,a-1]
c的枚举范围[b,a-1]
d的枚举范围[c,a-1]
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int n;
cin>>n;
for(int a=2; a<=n; a++)
for(int b=2; b<a; b++)
for(int c=b; c<a; c++)
for(int d=c; d<a; d++)
if(a*a*a==b*b*b+c*c*c+d*d*d) {
cout<<"Cube = "<<a<<", "<<"Triple = "<<"("<<b<<","<<c<<","<<d<<")"<<endl;
}
return 0;
}
例题2：生理周期
POJ1006
人生来就有三个生理周期，分别为体力、感情和智力周期，它们的周期长度为23天、28天和33天。每一个周期中有一天是高峰。在高峰这天，人会在相应的方面表现出色。例如，智力周期的高峰，人会思维敏捷，精力容易高度集中。因为三个周期的周长不同，所以通常三个周期的高峰不会落在同一天。对于每个人，我们想知道何时三个高峰落在同一天。对于每个周期，我们会给出从当前年份的第一天开始，到出现高峰的天数（不一定是第一次高峰出现的时间）。你的任务是给定一个从当年第一天开始数的天数，输出从给定时间开始（不包括给定时间）下一次三个高峰落在同一天的时间（距给定时间的天数）。例如：给定时间为10，下次出现三个高峰同天的时间是12，则输出2（注意这里不是3）。
输入：
输入四个整数：p, e, i和d。 p, e, i分别表示体力、情感和智力高峰出现的时间（时间从当年的第一天开始计算）。d 是给定的时间，可能小于p, e, 或 i。 所有给定时间是非负的并且小于365, 所求的时间小于21252。
当p = e = i = d = -1时，输入数据结束。
输出：
从给定时间起，下一次三个高峰同天的时间（距离给定时间的天数）。
采用以下格式：
Case 1: the next triple peak occurs in 1234 days.
注意：即使结果是1天，也使用复数形式“days”。
样例输入：
0 0 0 0
0 0 0 100
5 20 34 325
4 5 6 7
283 102 23 320
203 301 203 40
-1 -1 -1 -1
样例输出：
Case 1: the next triple peak occurs in 21252 days.
Case 2: the next triple peak occurs in 21152 days.
Case 3: the next triple peak occurs in 19575 days.
Case 4: the next triple peak occurs in 16994 days.
Case 5: the next triple peak occurs in 8910 days.
Case 6: the next triple peak occurs in 10789 days.
解题思路：
从d+1天开始，一直试到第21252天，对其中每个日期k，看是否满足:
(k – p)%23 == 0 && (k – e)%28 == 0 && (k – i)%33 == 0
在判断这个高峰时间是不是情商高峰时间；不是就将体力高峰时间增加23（也就是下一个体力高峰时间）
如果是情商高峰时间（说明也是体力高峰时间）;
也是先判断是不是智商高峰时间；不是就将智商个体力高峰时间增加23*28(也就是下一个情商个体力高峰时间）；
#include <iostream>
using namespace std;
int main() {
int p,e,i,d;
int num = 1;
while(cin>>p>>e>>i>>d&&p!=-1) {
int k;
for(k = d+1; (k-p)%23; k++); //找到体力高峰时间
for(; (k-e)%28; k +=23); //找到情商高峰时间
for(; (k-i)%33; k +=28*23); //找到智商也出现的时间；
cout <<"Case "<<num<<": the next triple peak occurs in "<<k-d<<" days."<<endl;
num++;
}
return 0;
}
例题3：称硬币：
POJ1013
题目描述：有12枚硬币。其中有11枚真币和1枚假币。假币和真币重量不同，但不知道假币比真币轻还是重。现在，用一架天平称了这些币三次，告诉你称的结果，请你找出假币并且确定假币是轻是重(数据保证一定能找出来)。
(注意:天平左右的硬币数总是相等的，even,up,down指的是天平右侧的状态)
输入样例
2
ABCD EFGH even
ABCI EFJK up
ABIJ EFGH even
ABCD IJKL even
ABCE GJKL even
ABCF AGKL up
输出样例
K is the counterfeit coin and it is light.
F is the counterfeit coin and it is heavy.
解题思路：
对于每一枚硬币先假设它是轻的，看这样是否符合称重结果。如果符合，问题解决。如果不符合，假设它是重的，看是否符合称重结果，如果符合，问题解决。把所有的硬币都试一遍。
//方法一
#include <stdio.h>
#include <string.h>
char right[3][7]; //存天平右边硬币 题目中共12个硬币，所以两侧最多各6个
char left[3][7]; //存左边
char result[3][7]; //存结果即天平右侧的状态
//判断假设是否成立的函数，light为1表示假设假币为轻，否则假设假币为重
char pleft[7];
char pright[7];
int IsFake(char c, int light) {
for (int i = 0; i < 3; i++) {
char *pleft,*pright;//指向天平两边的字符串
if (light) {
pleft = left[i];
pright = right[i];
} else { //如果假设假币是重的，则把称量结果左右对换
pleft = right[i]; //为了后面switch语句写一次，如果假币是重的就对换结果
pright = left[i];
}
switch (result[i][0]) { //天平右边的情况
case 'u': //右边的轻，那么轻的假币应该出现在右侧天平
if (strchr(pright,c) == NULL) //如果为NULL说明不符合
return 0; //说明假设c为轻的假设是错误的
break;
case 'e': //平衡，所以假币不能出现在任何一侧
if (strchr(pleft, c) || strchr(pright, c))
return 0;
break;
case 'd': //右边的重，假币应该出现在左侧
if (strchr(pleft, c) == NULL)
return 0;
break;
}
}
return 1;
}
int main() {
int t; //测试数据的组数
scanf("%d", &t);
while (t--) {
for (int i = 0; i < 3; i++)
scanf("%s %s %s", left[i], right[i], result[i]);
for (char c = 'A'; c <= 'L'; c++) { //题目中共12枚硬币
if (IsFake(c, 1)) { //假设c为轻的假币
printf("%c is the counterfeit coin and it is light.\n", c);
break;
} else if (IsFake(c, 0)) { //假设c为重的假币
printf("%c is the counterfeit coin and it is heavy.\n", c);
break;
}
}
}
return 0;
}
//方法二
#include <cstdio>
char left[3][7],right[3][7],result[3][7];
int status[12];
bool balanced() {
int i,k,leftw,rightw;
for( i=0; i<3; i++) {
leftw=rightw=0;
for( k=0; k<6&&left[i][k]!=0; k++) {
leftw += status[left[i][k]-'A'];
rightw += status[right[i][k]-'A'];
}
if(leftw>rightw&&result[i][0]!='u')
return false;
if(leftw==rightw&&result[i][0]!='e')
return false;
if(leftw<rightw&&result[i][0]!='d')
return false;
}
return true;
}
int main() {
int n;
scanf("%d",&n);
while(n--) {
int i;
for(i=0; i<3; i++)
scanf("%s %s %s",left[i],right[i],result[i]);
for( i=0; i<12; i++)
status[i]=0;
for( i=0; i<12; i++) {
status[i]=1;//第i枚硬币是较重的假币
if(balanced())
break;
status[i]=-1;//第i枚硬币是较轻的假币
if(balanced())
break;
status[i]=0;//第i枚硬币是真币
}
printf("%c is the counterfeit coin and it is %s.\n",i+'A',status[i]>0?"heavy":"light");
}
return 0;
}
洛谷P2392
kkksc03考前临时抱佛脚
题目描述
这次期末考试，kkksc03 需要考 4 科。因此要开始刷习题集，每科都有一个习题集，分别有 s1,s2,s3,s4 道题目，完成每道题目需要一些时间，可能不等 A1,A2,…,As1，B1,B2,…,Bs2，C1,C2,…,Cs3，D1,D2,…,Ds4。
kkksc03 有一个能力，他的左右两个大脑可以同时计算 2 道不同的题目，但是仅限于同一科。因此，kkksc03 必须一科一科的复习。
由于 kkksc03 还急着去处理洛谷的 bug，因此他希望尽快把事情做完，所以他希望知道能够完成复习的最短时间。
输入格式
本题包含 5 行数据：第 1 行，为四个正整数 s1,s2,s3,s4。
第 2 行，为 A1,A2,…,As1 共 s1 个数，表示第一科习题集每道题目所消耗的时间。
第 3 行，为 B1,B2,…,Bs2 共 s2 个数。
第 4 行，为 C1,C2,…,Cs3 共 s3 个数。
第 5 行，为 D1,D2,…,Ds4 共 s4 个数，意思均同上。
输出格式
输出一行，为复习完毕最短时间。
输入样例
1 2 1 3
5
4 3
6
2 4 3
输出样例
20
数据范围
1 ≤ s1, s2, s3, s4 ≤ 20。
1 ≤ A1,A2,…,As1,B1,B2,…,Bs2,C1,C2,…,Cs3,D1,D2,…,Ds4≤60。
解题思路：
看到一位
大佬
写的特别好，很仔细，我借鉴一下。
根据样例数据，我们来模拟一下 DFS 的过程。有左脑和右脑可用。每次我们都先用左脑，再用右脑，也就是这样的搜索过程：先全部左脑（方案一）、左1左2（左脑解第一题和第二题）、左1右1、左2右1和右1有2，这么四种组合。
第一个科目
有一题，所以我们可以得到：
1、全左脑：耗时 5。
2、全右脑：耗时 5。
因此第一个科目的最小时间为 5 分钟。
第二个科目
有两题，所以我们可以得到：
1、全左脑：耗时 4+3=7。
2、左脑解题1，右脑解题2：耗时 max(4,3)=4。
3、左脑解题2，右脑解题1：耗时 max(3,4)=4。
4、全右脑：耗时 4+3=7。
因此第二个科目的最小时间为 4 分钟。
第三个科目
有一题，所以我们可以得到：
1、全左脑：耗时 6。
2、全右脑：耗时 6。
因此第三个科目的最小时间为 6 分钟。
第四个科目
有三题，所以我们可以得到：
1、全部左脑完成。这样耗时为 2+4+3=9。
2、左脑完成1、2题，右脑完成3题。这样耗时是 max(2+4, 3)=6。
3、左脑完成1、3题，右脑完成2题。这样耗时是 max(2+3, 4)=5。
4、左脑完成1题，右脑完成2、3题。这样耗时是 max(2, 4+3)=7。
5、左脑完成2 3题，右脑完成1题。这样耗时是 max(4+3, 2)=7。
6、左脑完成2题，右脑完成1、3题。这样耗时是 max(4, 3+2)=5。
7、左脑完成3题，右脑完成1、2题。这样耗时是 max(3, 2+4)=6。
8、全部右脑完成。这样耗时为 2+4+3=9。
因此第四个科目的最小时间为 5 分钟。
这里我们可以看到就是枚举题目分配给两个脑子所有可能组合。如果数据量大，我们可以使用减枝技巧。如上描述的过程，有一半是浪费的。
总时间自然就是 5+4+6+5=20。
#include <iostream>
#include <algorithm>
using namespace std;
int s[5],a[5][25];
int l,r;
int m;
int ans=0;
void dfs(int x,int y) {
if(y>s[x]) {//判断结束
m=min(m,max(l,r));
return ;
}
l=l+a[x][y];//左脑工作
dfs(x,y+1);
l=l-a[x][y];
r=r+a[x][y];//右脑工作
dfs(x,y+1);
r=r-a[x][y];
}
int main() {
cin>>s[1]>>s[2]>>s[3]>>s[4];
for(int i=1; i<5; i++) {
m=99999;
l=0,r=0;//左右脑清零
for(int j=1; j<=s[i]; j++)
cin>>a[i][j];
dfs(i,1);//从第i门的第一题开始复习
ans+=m;
}
cout<<ans<<endl;
return 0;
}