DFS总结

公共模版

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;
}