P3486 - 天平-【2014暑期训练】T5Day2T1

内存限制：256 MB 时间限制：1 S 标准输入输出

题目类型：传统评测方式：文本比较上传者：

提交：1 通过：1

提交提交记录统计 Web Board

天平

【问题描述】

一座天平有n个砝码，每个砝码的重量为W_i(longint以内)，按重量从小到大排列，而且从第三个砝码开始，每个砝码重量至少为前两个砝码重量和，即Wi>=W_i-1+ W_i-2 。

天平的最大承受重量为C（longint以内），称重时选取若干个砝码放到天平上，这些砝码的重量和不能超过这个C。

求最大可以放置的砝码的重量和。

【文件输入】

第一行，两个用空格隔开的整数n,C；

接下来n行，每行有一个整数Wi。

【文件输出】

一个整数，代表最大组合重量

【输入样例】

3 15

【输出样例】

【数据规模】

对于20%数据，n<=16；

对于另外的30%数据，C<=100000；

对于100%的数据，n<=1000，C在longint以内

裸的暴力是肯定不能过的，要加剪枝
设当前做到i，组合值为have,
后面所有值的和为sum[i]，已得到的最优为ans;

if have+w[i]>c then 直接返回
if have+sum[i]<=ans then 直接返回

然后，因为越往后砝码重量越大，所以如果从小到大搜索，那么很容易有
Have+sum[i]>ans 第二条剪枝相当于不存在
只要从大到小搜就没有这个问题了。（但第一条剪枝就不能直接返回了）

稳定的2n/2算法
我们发现，对于题目条件的利用还是太少了
Sum[i]表示前缀和
其实有 w[i+2]+w[2]>=sum[i], 即w[i+2]>sum[i]

我们把还能装的容量记为left
则从后往前搜索时有三种情况：
1. left<w[i]，直接不取
2. left>=w[i]+w[i-1]，假设i不取，则w[i]+w[i-1]>w[i-1]+sum[i-2]=sum[i-1]，还不如只取i和i-1,换言之，这种情况i砝码必须取。
3. w[i]<=left<w[i]+w[i-1]，i和i+1不能都取，那么假设他们都不取，则w[i]>sum[i-2]，还不如只取i，换言之，这种情况必须取i或i-1
第一，二种情况不浪费复杂度
第三种情况对于两个数有两种选择
则最坏情况下遇到的都是情况三

复杂度为严格的2n/2

模拟赛-2014暑期训练

3486: 天平-【2014暑期训练】T5Day2T1

题目描述

数据范围与提示

分类标签