题解 P3052 【摩天大楼里的奶牛】

mzq667 · 2017-06-18 07:13:47 · 题解

此题一般思路为迭代加深。关键是枚举车厢数，再dfs奶牛号，每次递归遍历车厢号，看奶牛能进哪个车厢，就把它放进去，然后继续dfs（千万不要枚举奶牛号，然后往车厢里塞奶牛）。还有剪枝，可证第i奶牛放到i后车厢没有意义。即可得出答案。

代码：

#include <cstdio>
#include <algorithm>
using namespace std;
int n, m, c[19], tot(0), ans(0), v[19];
bool dfs(int x, int num){//x为奶牛号， num为车厢数
    for (int i = 1; i <= x && i <= num; ++i)//for车厢号，看奶牛能被放进哪个车厢
        if(v[i] + c[x] <= m){
            v[i] += c[x];
            if(x == n) return 1;
            if(dfs(x+1, num)) return 1;
            v[i] -= c[x];
        }
    return 0;
}
int main(){
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; ++i) scanf("%d", &c[i]);
    for (int i = 1; i <= n; ++i){//枚举车厢数
        fill(v+1, v+n+1, 0);//当然也可以memset
        if (dfs(1, i)){
            printf("%d\n", i);
            break;
        }
    }
    return 0;
}