公共模版
int maxv=-INF；
//最优值设为全局变量
inline void DFS(int i,int x1,...,int xn)
//i用来控制层数，作为边界条件的判断依据，x1...xn是最优化变量或与其相关的量
{
.......
}
括号里面的内容视以下三种而定，最后会给出总结
1. 每一层必须选一个
思路：先加上当前的值，然后边界判断，如果满足最优，更新最优值，返回程序，执行该步骤的下一个状态，比如在例题中可以选择(x+1,y)和(x+1,y+1)就执行下一个状态的dfs，之后恢复原来的变量值（恢复到未选择之前的状态，因为还有其他的下一个状态要跑）
例题：
从顶层开始向下走，每走下一级，可向左下方向或右下方向走。求走到底层后它所经过数字的总和的最大值。
【输入格式】
第一个整数为n,一下n行为各层的数字。
【输出格式】
一个整数，即最大值。
【输入样例 】
5
1
6 3
8 2 6
2 1 6 5
3 2 4 7 6
【输出样例】
23
【样例说明】
最大值=1+3+6+6+7=23
void dfs(int i,int j){
sum+=a[i][j];
if(i==N)
{
if(sum>Max)
Max=sum;
return ;
}
for(int x=0;x<2;x++){
dfs(i+1,j+x);
sum-=a[i+1][j+x];
}
2. 任何一步都可选可不选
分析：这一步其实是上一步的变种，变化在于首先不能从第一步开始，因为第一步是可以不选的，其次因为每一步都是可选可不选的，其实可以看成每一个的下一步都有两种状态可以转移，一个是选择了这种状态的，一个是没选的
思路：先进行边界判断，若比最优值还优则更新，返回。
dfs(i+1,x1);
dfs(i+1,x1+a
例题：
洛谷P2036(洛谷P2677也很经典)
#define N 2000000000
using namespace std;
int minv=N;
int n;
vector<int> acid,sweet;
void dfs(int i,int sum,int mult,int sub)
{
if(i==n)
{
if(sub<minv)
minv=sub;
return;
}
dfs(i+1,sum+sweet[i+1],mult*acid[i+1],abs(sum+sweet[i+1]-mult*acid[i+1]));
dfs(i+1,sum,mult,sub);
}
int main()
{
cin>>n;
acid.resize(n+1);
sweet.resize(n+1);
for(int i=1;i<=n;i++)
{
cin>>acid[i]>>sweet[i];
}
dfs(0,0,1,N);
cout<<minv<<endl;
return 0;
}
