洛谷P3052 [USACO12MAR]摩天大楼里的奶牛Cows in a Skyscraper
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 <= W <= 100,000,000) pounds and cow i weighs C_i (1 <= C_i <= W) pounds. Please help Bessie figure out how to get all the N (1 <= N <= 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.
给出n个物品,体积为w[i],现把其分成若干组,要求每组总体积<=W,问最小分组。(n<=18)
输入输出格式
输入格式:
Line 1: N and W separated by a space.
- Lines 2..1+N: Line i+1 contains the integer C_i, giving the weight of one of the cows.
输出格式:
Line 1: A single integer, R, indicating the minimum number of elevator rides needed.
- Lines 2..1+R: Each line describes the set of cows taking
one of the R trips down the elevator. Each line starts with an integer giving the number of cows in the set, followed by the indices of the individual cows in the set.
输入输出样例
4 10
5
6
3
7
3
2 1 3
1 2
1 4
说明
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;
#define maxn 20
int n,m,a[maxn],b[maxn],mid;
bool flag=;
void dfs(int pos,int num){
if(pos==n+){
flag=;
return;
}
if(flag)return;
for(int i=;i<=num;i++){
if(m-b[i]>=a[pos]){
b[i]+=a[pos];
dfs(pos+,num);
b[i]-=a[pos];
}
}
if(num==mid)return;
b[num+]=a[pos];
dfs(pos+,num+);
b[num+]=;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)scanf("%d",&a[i]);
int ans=n,l=,r=n;
while(l<=r){
mid=(l+r)>>;
memset(b,,sizeof(b));
flag=;
dfs(,);
if(flag)ans=mid,r=mid-;
else l=mid+;
}
printf("%d",ans);
}
100分 迭代加深搜索(二分深度)
/*
f 数组为结构体
f[S].cnt 表示集合 S 最少的分组数
f[S].v 表示集合 S 最少分组数下当前组所用的最少容量
f[S] = min(f[S], f[S - i] + a[i]) (i ∈ S)
运算重载一下即可。
*/
#include<cstdio>
#include<iostream>
int n,m,w;
int a[];
struct node{
int cnt,v;
node operator + (const int b)const{
node res;
if(v+b<=w)res.cnt=cnt,res.v=v+b;
else res.cnt=cnt+,res.v=b;
return res;
}
bool operator < (const node b)const{
if(cnt==b.cnt)return v<b.v;
return cnt<b.cnt;
}
}f[<<];
node min(node x,node y){
if(x<y)return x;
return y;
}
node make_node(int x,int y){
node res;
res.cnt=x;res.v=y;
return res;
}
int main(){
int sta;
scanf("%d%d",&n,&w);
m=(<<n)-;
for(int i=;i<=n;i++)scanf("%d",&a[i]);
for(sta=;sta<=m;sta++){
f[sta]=make_node(1e9,w);
for(int i=;i<=n;i++){
if(!((<<i-)&sta))continue;
f[sta]=min(f[sta],f[(<<i-)^sta]+a[i]);
}
}
printf("%d",f[m].cnt+);
return ;
}
100分 状压dp
最新文章
- 【Win 10应用开发】响应系统回退键的导航事件
- Java面向对象一
- codevs 4543 treap 模板
- js日期显示效果
- linux命令--nslookup
- 清北学堂模拟day6 兔子
- android之进度条组件ProgressBar
- word-break:brea-all;word-wrap:break-word的区别
- (12)odoo各种提前期和时间
- ASP.Net软件工程师基础(四)
- python--把一个方法变成属性调用
- [ios2]componentsSeparatedByCharactersInSet使用方法
- 增强学习 | Q-Learning
- rls与rlsd
- js编码函数一些区别
- java的InputStream和OutputStream的理解
- selenium无界面chromedriver
- Java调用Python脚本工具类
- centos7防火墙操作
- [转载].net程序集自动生成版本号