P3052 [USACO12MAR]摩天大楼里的奶牛（迭代加深搜索）

（已经一句话了）

第一反应：暴力

第二反应：朴素算法过不去

第三反应：没法折半暴搜（没法统计答案）

所以，歪歪了一个类似贪心刷表的方法，过了这道题。

首先，如果爆搜的话会有几个状态：

1. 当前牛
2. 当前几个箱子
3. 当前的牛数量

而且它的复杂度是阶乘级别。

发现这道题目有显然单调性（答案处在分界线，-1不合法，+1不是最优）所以歪歪了一个类似二分check的dfs方法。

那么状态就得改变了。传入的还是牛的编号，但是，在dfs内部，枚举的是当前的牛放在哪个箱子里。如果能搜到最后一步，就返回。

于是乎，这样dfs可能会搜很多没用的，（例如答案是2，但是会搜9,4,2），而且范围非常小，可以直接枚举），搜到就跳出，输出。

这个就是迭代加深了。这里把这个词拆开，一个是迭代（这里就是指枚举答案），加深就是在一次一次加深状态。

于是给出代码：

#include<bits/stdc++.h>

using namespace std;

const int maxn=;

int n,w;

int ans;

int a[maxn];

int vis[maxn];

int flag=;

int f[maxn];

void dfs(int x)

{

    if(x==n)

    {

        flag=;

        return;

    }

    for(int i=;i<=ans;i++)

    {

        if(f[i]+a[x]<=w)

        {

            f[i]+=a[x];

            dfs(x+);

            f[i]-=a[x];

            if(flag)

            return;

        }

    }

}

int mx=;

bool cmp(int a,int b)

{return a>b;}

int main()

{

    //freopen("catclimb.in","r",stdin);

    //freopen("catclimb.out","w",stdout);

    scanf("%d%d",&n,&w);

    for(int i=;i<=n;i++)

    {

        scanf("%d",&a[i]);

        mx+=a[i];

    }

    sort(a+,a+n+);

    for(ans=mx%w==? mx/w:mx/w+;ans<=;ans++)

    {

        dfs();

        if(flag==)

        {

            printf("%d",ans);

            return ;

        }

    }

    return ;

}