（已经一句话了）
第一反应：暴力
第二反应：朴素算法过不去
第三反应：没法折半暴搜（没法统计答案）
所以，歪歪了一个类似贪心刷表的方法，过了这道题。
首先，如果爆搜的话会有几个状态：
而且它的复杂度是阶乘级别。
发现这道题目有显然单调性（答案处在分界线，-1不合法，+1不是最优）所以歪歪了一个类似二分check的dfs方法。
那么状态就得改变了。传入的还是牛的编号，但是，在dfs内部，枚举的是当前的牛放在哪个箱子里。如果能搜到最后一步，就返回。
于是乎，这样dfs可能会搜很多没用的，（例如答案是2，但是会搜9,4,2），而且范围非常小，可以直接枚举），搜到就跳出，输出。
这个就是迭代加深了。这里把这个词拆开，一个是迭代（这里就是指枚举答案），加深就是在一次一次加深状态。
于是给出代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn=505;
int n,w;
int ans;
int a[maxn];
int vis[maxn];
int flag=0;
int f[maxn];
void dfs(int x)
{
if(x==n)
{
flag=1;
return;
}
for(int i=1;i<=ans;i++)
{
if(f[i]+a[x]<=w)
{
f[i]+=a[x];
dfs(x+1);
f[i]-=a[x];
if(flag)
return;
}
}
}
int mx=0;
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=1;i<=n;i++)
{
scanf("%d",&a[i]);
mx+=a[i];
}
sort(a+1,a+n+1);
for(ans=mx%w==0? mx/w:mx/w+1;ans<=18;ans++)
{
dfs(0);
if(flag==1)
{
printf("%d",ans);
return 0;
}
}
return 0;
}
P3052 [USACO12MAR]摩天大楼里的奶牛（迭代加深搜索，IDA*）
原文：https://www.cnblogs.com/ajmddzp/p/11815707.html