「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.

 

思路

存在性状压DP,记得转移的时候要判一下存在性

 

代码

#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;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注