题目背景

白露横江，水光接天，纵一苇之所如，凌万顷之茫然。——苏轼

真程海洋近来需要进购大批赛斯石，你或许会问，什么是赛斯石？

首先我们来了解一下赛斯，赛斯是一个重量单位，我们用$si$作为其单位。比如$1$赛斯就是$1si$。

而赛斯石有这样一个性质，它本来是一赛斯一赛斯单独存在的，但是用自然枪将其精化之后，它就会与其它经过精化的赛斯石进行合并，合并到合适的重量之后，便将其钝化，使其不再合并其它赛斯石，如果合错了，也可以用金刚刀将其切开（神奇的是你只能切成整数赛斯重量）。赛斯石的重量只能是整数赛斯重量，而不同赛斯重量的赛斯石的价格也是不一样的。

题目描述

现需上市$Need$赛斯重量的赛斯石，卖家想算出这些赛斯石经过某种合并方式来获得的最大收益。然而目前有一个问题，市场在真程大殿附近（真程海洋中心位置），卖家需要租船送赛斯石过去（即不考虑卖家自己租船过去的费用），目前有十种船可以租，载重量从$1si$到$10si$，每艘船的租价也是有所不同的，如下表所示：

由于真程大殿附近有强烈的赛斯力，导致无法对赛斯石进行任何操作，商家将赛斯石运过来之后就只能按照之前合并好的卖。假设卖家不返回，且这些赛斯石全部能卖出去。现在卖家他要计算总盈利（设总盈利=赛斯石的总收益-租船所需总费用），请你设计一个程序，算出一种最佳方案，以获得最大总盈利。

输入输出格式

输入格式：

输入一共有两行

第一行有一个数据$Need$（赛斯石的总量，单位：$si$）

第二行有十个数据a_{1}\ …\ a_{10}a1​ ... a10​（分别为$1si$到$10si$的赛斯石市场价格，单位：元）

输出格式：

输出仅一行，包含一个整数，表示最大总盈利。

输入输出样例

11
1 6 11 17 23 27 33 35 38 43

32

7
1 5 14 18 20 28 31 34 39 42

21

说明

样例一说明：

将$11$个单位赛斯石合并为一个$4si$的赛斯石和一个$7si$的赛斯石并且租两个载重分别为$4si$和$7si$的船，这样做为最佳方案，那么最大总盈利就是$32$元。

注意：

对于所有输入数据，均在区间$(0,100000)$中，并且为整数；

保证卖家最大总盈利为正；

同一行中，每两个数据之间有一个空格。

赛后强化版于$2017$年$11$月$9$日$8$点$10$分已强化完毕。

这道题与传统的背包问题的不同的地方在于可以用一个船载多个物品来降低运费。

按照比赛的设定，体积为a和体积为b的两个物品用载重a+b的船来运输比用a和b两艘船来运输便宜的情况只有4种

即

a=2 b=5

a=3 b=4

a=4 b=5

a=5 b=5

除此之外，每件物品单独用一艘船来运都是最便宜的。

那这样我们就可以把这4种情况当作新加的4个物品来看待，每个物品的体积分别是v[a]+v[b]，价值也是p[a]+p[b]

然后按照01背包来做就可以了

每件物品能够收益的数额就是价值减去运费

 

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll a[15];//存储每件物品的价值
ll b[11] = {0, 1, 3, 5, 7, 9, 10, 11, 14, 15, 17};
ll e[15];//存储每件物品的体积
ll c[100007];
int main() {
	ios::sync_with_stdio(0);
	int n;
	cin >> n;
	for (int i = 1; i <= 10; ++i) {
		cin >> a[i];
		e[i] = i;
	}
	a[11] = a[2] + a[5];
	e[11] = 7;
	a[12] = a[3] + a[4];
	e[12] = 7;
	a[13] = a[4] + a[5];
	e[13] = 9;
	a[14] = a[5] + a[5];
	e[14] = 10;
	
	for (int i = 1; i <= 14; ++i) {
		if(a[i] > 0)
			for(int j = e[i]; j <= n; j++) {
				c[j] = max(c[j], c[j - e[i]] + a[i] - b[e[i]]);
			}
	}
	cout << c[n] << endl;

}