DFS——剪枝

dfs在每个点（状态）的情况比较多，但是节点比较少的时候很常用，我们将每个状态的情况延伸出去，可以画出一棵搜索树。dfs会搜到每一种情况，所以我们实际上可以按照任意顺序来判否。为了优化搜索我们可以在搜索的过程中提前判否，那么显然越早判否，需要搜的规模就越小。那么如何实现尽可能地提前判否呢，那么就涉及到搜索顺序和剪枝技巧了，常用的剪枝技巧如下：

1.优化搜索顺序

（一般情况下，优先搜索分支较少的节点）

2.排除等效冗余

（如果选择顺序对结果没有影响的话，那么我们需要尽可能的避免等效情况的搜索）

3.可行性剪枝

4.最优性剪枝

（在求解最优的问题的时候，如果当前的情况已经大于等于搜到的最优解了，那么可以直接      剪枝）

5.记忆化搜索

（多用于dp问题，将算出来的状态储存下来，如果在搜索的过程中发现一个点的状态已经确      定，那么直接返回即可，不需要再往下搜了）

165. 小猫爬山(活动 - AcWing)

思路：我们一点一点来分析，首先n小于等于18，那么就说明这道题可以通过搜索来解决，搜索的时间复杂度是质数级别的，所以如果n太大了，那么用搜索的话时间复杂度或者空间复杂度就有点高了。

那么搜索题我们就要先确定一个合适的搜索顺序，合适的搜索顺序的要求就是可以搜到所有的情况。我们可以发现，这里dfs的每一层是用来确定一只小猫的位置，那么就这一层中的情况就很容易得到，有几种情况，首先是放在之前已经分配的车中，这里可以通过遍历那些车来实现，或者是新开一辆车，这样就可以将所有的情况都考虑到。我们将搜索树画出来：

 那么暴力搜索的思路就理通顺了，现在我们来考虑剪枝的问题，我们对照上面几条规则，一条一条来看：

1.优化搜索顺序，对应到这道题就是先搜重的猫还是先搜轻的猫，显然先搜重的猫比较好，因为重的猫可以占掉更多的空间，让后面的情况少一些。

2.排除等效冗余，这题的我们一层确定一个猫，所以不存在等效冗余的问题，至于车，每次都要遍历已经确定的点，所以没什么分别。

3.可行剪枝，如果放入当前猫之后已经超过上限了，肯定不用再搜了，所以可行性剪枝可以用

4.最优性剪枝，这题需要求的就是最优的问题，所以可以使用最优化剪枝。

5.记忆化搜索，每只猫与其他猫之间没有直接的关系，所以用不上记忆化搜索。

那么优化就确定出来了。

#include<bits/stdc++.h>
using namespace std;
int n,m;
int w[30],sum[30];
int ans;
void dfs(int u,int k)//k表示当前用了几辆车
{
    if(k>=ans) return;//最优性剪枝
    if(u==n)//下标从0->n-1，所以u==n时所有的猫都分配好了
    {
        ans=k;
        return ;
    }
    for(int i=0;i<k;i++)//车的下标也是从0开始，k表示已经用了k辆车了
    {
        if(sum[i]+w[u]<=m)//可行性剪枝
        {
            sum[i] += w[u];
            dfs(u+1,k);
            sum[i] -= w[u];//恢复现场
        }
    }
    sum[k]=w[u];
    dfs(u+1,k+1);
    sum[k]=0;//恢复现场
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++) scanf("%d",&w[i]);
    sort(w,w+n);
    reverse(w,w+n);
    ans=n;
    dfs(0,0);
    
    printf("%d",ans);
    return 0;
}

166. 数独（166. 数独 - AcWing题库）

思路:这题就是枚举每个空的位置可以填的数，然后当所有的空都填上数后，就输出结果。所以是一个可行性的搜索，而非最优化搜索。

现在的问题就在于如何快速获取每个位置填什么数，以及更新填完之后的状态。这里我们可以用一个二进制数来表示每行每列每个3*3的方格中的状态，比如，对于第i行，我们用row[i]表示一个二进制数，这个二进制数中如果某一位上是1，那么就说明这一位对应的数可以填进这一行，那么对于一个空格，我们只要将它的行列以及一个3*3的方格中的状态求&，那么就可以获得这个位置可以填哪些数，求&之后的结果是一个二进制数，所以我们要想得到每一位具体填什么还需要再处理一下。这里有一个处理的思路是，我们获取这个二进制数的lowbit，同时预处理出来所有的lowbit对应的数是哪一位。这样就可以很快获得这一位填什么数，然后所有问题解决就可以开始爆搜了。

但是我们还是要尽可能地优化：

1.优化搜索顺序，显然我们应该先搜索情况少的地方

2.排除等效冗余，这道题实际上不存在等效冗余，因为一个位置上的数填上后就改变了一个横竖以及3*3方格中的状态，所以两个数填的顺序不同，那么对应的状态是不等效的。

3.可行性剪枝，当一个位置搜不下去的时候及时返回false进行剪枝。

4.最优性剪枝，本题是求可行性问题，不存在最优化剪枝，所以不用考虑。

那么搜索和优化都考虑出来了，那么就可以开始写代码了。

#include<bits/stdc++.h>
using namespace std;
const int N=9,M=1<<N;
int row[N],col[N],cell[3][3];
char s[100];
int ones[M],mp[M];
void init()
{
    for(int i=0;i<N;i++) row[i]=col[i]=(1<<N)-1;
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++)
            cell[i][j]=(1<<N)-1;
}
void draw(int x,int y,int t,int sta)
{
    if(sta) s[x*N+y]='1'+t;
    else s[x*N+y]='.';
    
    int v=1<<t;
    if(!sta) v=-v;
    row[x] -= v;
    col[y] -= v;
    cell[x/3][y/3] -= v;
}

int get(int x,int y)
{
    return row[x] & col[y] & cell[x/3][y/3];
}
int lowbit(int x)
{
    return x&-x;
}
int dfs(int cnt)
{
    if(!cnt) return 1;
    
    int mi=10,x,y;
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
            if(s[i*N+j]=='.')
            {
                int sta=get(i,j);
                if(ones[sta]<mi)
                {
                    mi=ones[sta];
                    x=i,y=j;
                }
            }
            
    int state=get(x,y);
    for(int i=state;i;i-=lowbit(i))
    {
        int t=mp[lowbit(i)];
        draw(x,y,t,1);
        if(dfs(cnt-1)) return 1;
        draw(x,y,t,0);
    }
    return 0;
}
int main()
{
    for(int i=0;i<N;i++) mp[1<<i] = i;
    for(int i=0;i<1<<N;i++)
        for(int j=0;j<N;j++)
            ones[i]+=i>>j&1;
    
    while(cin>>s,s[0]!='e')
    {
        init();
        int cnt=0;
        for(int i=0,k=0;i<N;i++)
            for(int j=0;j<N;j++,k++)
                if(s[k]!='.')
                {
                    int t=s[k]-'1';
                    draw(i,j,t,1);
                }
                else cnt++;
        
        dfs(cnt);
        
        cout<<s<<endl;
    }
}

167. 木棒(167. 木棒 - AcWing题库)

思路：这道题要找出可能的最小长度，很容易想到二分，但是拼好后的木棍实际没有单调性，不过最终的长度一定是总长的因数，所以我们可以从这个角度进行优化。

当我们枚举出一个木棒长度后，就可以通过dfs来检查是否可以实现。那么就是长度固定，然后往里面填木棍，那么就是类似小猫爬山题，不过小猫爬山题不用把车填满，这里需要把木棒填满。但是那题中先填大的再填小的思路就可以用，这里就是第二个优化，我们先讨论长度长的木棍。

然后我们再来看，这里还有一点，在小猫题中，每层可以确定一个小猫的位置，所以我们是在每层中枚举出所有已经讨论过的车，但是这里每根木棒都要填满，所以我们就不能以木棍作为讨论的中心，而是应该以木棒作为讨论的中心，对于木棍，讨论它是否能填入当前木棒，当一根木棒填满后再重开一根新的木棒。 一根木棒一根木棒填，因为这里需要将每根木棒填满。所以这里由引出一个优化，在木棒内部木棍的顺序无所谓，所以我们需要按照组合数的思路来填每根木棒。也就是如果当前不新开，那么就直接往后讨论，如果新开那么再从头开始看。这是第三个优化。

然后我们再来看，如果当前木棍可以加入当前木棒，但是往后搜，最终返回的结果是否的话，那么所有和当前木棍相同的木棍都不能填在这里，因为如果可以，那么这里填的一定可以变成我们判否的那个，这是第四个优化。

继续看，如果我们新开了一个，然后某个木棍放在它的第一位，但是往后搜判否了，那么木棒这个长度的情况就应该全部判否。可以这么来思考，如果对于这个木棒有一种合适的方案，那么当前这根木棍一定得放在后面某根木棒的中间位置，木棒内部的位置无所谓，那么就可以将这个木棍换到那根木棒的开头位置，然后又可以将那根木棒换到当前判否的这根木棒的位置，那么就矛盾了，所以如果一根木棒开头位置放一根木棍往后搜判否了，那么这个长度的情况就应该判否。这是第五个优化。

最后一个优化：如果在一个木棒的结尾填入一个木棍，然后往后搜判否了，那么这个长度就应该判否。因为很显然这里如果填满，肯定得填若干个长度和与这个木棍长度相等的木棍，那么就可以替换成这个木棍，又产生矛盾。所以如果这个木棍填在最后一个位置但是判否的话，这个木棒的长度就应该判否。

那么搜索和优化就都讨论结束了，可以来写代码了。

#include<bits/stdc++.h>
using namespace std;
int n,sum,len;
int a[70];
int st[70];
int dfs(int u,int k,int start)
{
    if(u*len == sum) return 1;
    if(k==len) return dfs(u+1,0,0);
    
    for(int i=start;i<n;i++)
    {
        if(st[i] || k+a[i]>len) continue;
        
        st[i]=1;
        if(dfs(u,k+a[i],i+1)) return true;
        st[i]=0;
 
        if(!k) return false;
            
        if(k+a[i]==len) return false;
            
        int j=i;
        while(j<n&&a[j]==a[i]) j++;
        i=j-1;
    }
    return false;
}
int main()
{
    while(cin>>n)
    {
        if(!n) break;
        memset(st,0,sizeof st);
        sum=0;
        for(int i=0;i<n;i++) scanf("%d",&a[i]),sum+=a[i];
        sort(a,a+n);
        reverse(a,a+n);
        len=1;
        while(1)
        {
            if(sum%len==0&&dfs(0,0,0))
            {
                cout<<len<<endl;
                break;
            }
            len++;
        }
    }
}

168. 生日蛋糕(168. 生日蛋糕 - AcWing题库)

思路：M比较小，那么暗示我们需要对于每一层来枚举r和h，肯定不能随便枚举，题目有一些限制条件，我们据此将每一层的r和h限定一下，缩小搜索范围。

为了使搜索分支尽可能的小，那么我们可以从底层往上搜，而且因为r对体积的贡献是平方级别的，我们先枚举r，再枚举h，不过我们还是将底层设为第m层，顶层设为第1层，那么对于每层来说：
i<=r[i]<r[i+1] ，对于左边界，我们是假设后面都严格递减，那么如果半径小于i的话，就不能保证顶层也是正整数了，对于右边界，就是为了符合递减的要求。但仅仅有这些还是不够的。我们假设已经讨论的部分的体积是v，那么剩余的体积应该是n-v,所以我们假设这个体积全部分到这一层，h为1，那么半径就是sqrt(n-v)，这是另一个上限。故i<=r[i]<=min(r[i+1]-1,sqrt(n-v))
对于h也是一样的，i<=h[i]<=min(h[i+1]-1,(n-v)/r)

仅仅剪枝到这里还是不够的，我们假设当前已经填了体积为v的部分了，然后剩下的部分我们按照最小体积来计算（最小体积可以预处理出来），如果和已经超过n了，那么就不用讨论了，对于表面积也是一样，如果已经超过了ans，就不用再讨论了。

然后还有一个很关键但是很难想的优化,因为这里用到了放缩：

至此，搜索和优化都讨论好了，那么来写代码。

#include<bits/stdc++.h>
using namespace std;
int n,m;
int miv[30],mis[30];
int ans=1e9;
int r[30],h[30];
void dfs(int u,int v,int s)
{
    if(v+miv[u]>n) return;
    if(s+mis[u]>=ans) return;
    if(s+2*(n-v)/r[u+1]>=ans) return;
    if(!u) 
    {
        if(v==n) ans=s;
        return;
    }
    for(int i=min(r[u+1]-1,(int)sqrt(n-v));i>=u;i--)
    {
        for(int j=min(h[u+1]-1,(n-v)/i/i);j>=u;j--)
        {
            int t=0;
            if(u==m) t=i*i;
            h[u]=j,r[u]=i;
            dfs(u-1,v+i*i*j,s+2*i*j+t);
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        miv[i] = miv[i-1] + i*i*i;
        mis[i] = mis[i-1] + 2*i*i;
    }
    r[m+1]=h[m+1]=1e9;
    dfs(m,0,0);
    if(ans==1e9) cout<<0;
    else cout<<ans;
}

这一块儿反映出来的问题就是不熟练，思路和代码都不太熟练，所以继续练吧！