「NOIP模拟赛」小猫爬山
题目描述
Freda和rainbow饲养了N只小猫，这天，小猫们要去爬山。经历了千辛万苦，小猫们终于爬上了山顶，但是疲倦的它们再也不想徒步走下山了（呜咕>_<）。
Freda和rainbow只好花钱让它们坐索道下山。索道上的缆车最大承重量为W，而N只小猫的重量分别是C1、C2……CN。当然，每辆缆车上的小猫的重量之和不能超过W。每租用一辆缆车，Freda和rainbow就要付1美元，所以他们想知道，最少需要付多少美元才能把这N只小猫都运送下山？
输入格式
第一行包含两个用空格隔开的整数，N和W。
接下来N行每行一个整数，其中第i+1行的整数表示第i只小猫的重量C i。
输出格式
输出一个整数，最少需要多少美元，也就是最少需要多少辆缆车。
样例输入
5 1996
1
2
1994
12
29
样例输出
2
数据范围与约定
对于100%的数据，1<=N<=18，1<=C i <=W<=10^8。
题解
迭代深搜，最好先排个序。。。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<cstring> #include<map> #include<algorithm> #define ll long long using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } bool flag; int n,w,deep,sum; int c[20],b[20]; void dfs(int x) { if(x==n+1){flag=1;return;} for(int i=1;i<=deep;i++) if(b[i]+c[x]<=w) { b[i]+=c[x]; dfs(x+1); b[i]-=c[x]; if(flag)return; } return; } int main() { //freopen("catclimb.in","r",stdin); //freopen("catclimb.out","w",stdout); n=read();w=read(); for(int i=1;i<=n;i++)c[i]=read(),sum+=c[i]; sort(c+1,c+n+1,greater<int>()); for(deep=sum/w;deep<=18;deep++) { dfs(1); if(flag) { printf("%d\n",deep); return 0; } } return 0; } |
Subscribe
计数器 9775144
OI 课件=>
OI 课件=>