# 「Luogu P3052」 [USACO12MAR]摩天大楼里的奶牛Cows in a Skyscraper

「Luogu P3052」 [USACO12MAR]摩天大楼里的奶牛Cows in a Skyscraper

## 题目描述

A little known fact about Bessie and friends is that they love stair climbing races. A better known fact is that cows really don’t like going down stairs. So after the cows finish racing to the top of their favorite skyscraper, they had a problem. Refusing to climb back down using the stairs, the cows are forced to use the elevator in order to get back to the ground floor.

The elevator has a maximum weight capacity of $W (1 \leq W \leq 100,000,000)$pounds and cow i weighs $C_i (1 \leq C_i\leq W)$pounds. Please help Bessie figure out how to get all the $N (1 \leq N \leq 18)$ of the cows to the ground floor using the least number of elevator rides. The sum of the weights of the cows on each elevator ride must be no larger than $W$.

## 输入输出格式

### 输入格式

* Line $1$:$N$ and $W$ separated by a space.

* Lines $2\dots 1+N$: Line $i+1$ contains the integer $C_i$, giving the weight of one of the cows.

### 输出格式

* A single integer, $R$, indicating the minimum number of elevator rides needed.

one of the $R$ trips down the elevator.

## 输入输出样例

### 输入样例#1

4 10
5
6
3
7


### 输出样例#1

3


## 说明

There are four cows weighing $5, 6, 3,$ and $7$ pounds. The elevator has a maximum weight capacity of $10$ pounds.

We can put the cow weighing $3$ on the same elevator as any other cow but the other three cows are too heavy to be combined. For the solution above, elevator ride $1$ involves cow #1 and #3, elevator ride 2 involves cow #2, and elevator ride $3$ involves cow #4. Several other solutions are possible for this input.

## 代码

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

int n, w[19], f[20][1<<19], W;

int main(){
memset(f, 0x3f3f3f3f, sizeof(f));
scanf("%d%d", &n, &W);
for(int i=1; i<=n; i++)
scanf("%d", &w[i]), f[1][1<<(i-1)]=w[i];
f[1][0]=0;
for(int i=1; i<=n; i++){
for(int j=0; j<(1<<n); j++)
if(f[i][j]!=0x3f3f3f3f)
for(int k=1; k<=n; k++)
if(W-f[i][j]>=w[k] && (j&(1<<(k-1)))==0)
f[i][j|(1<<(k-1))]=min(f[i][j|(1<<(k-1))], f[i][j]+w[k]);
else
f[i+1][j|(1<<(k-1))]=min(f[i+1][j|(1<<(k-1))], w[k]);
if(f[i][(1<<n)-1]!=0x3f3f3f3f){
cout<<i<<endl;
return 0;
}
}
return 0;
}