P3983 赛斯石（赛后强化版），背包

题目背景

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

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

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

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

题目描述

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

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

输入格式

输入一共有两行

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

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

输出格式

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

输入输出样例

输入 #1复制

11
1 6 11 17 23 27 33 35 38 43

输出 #1复制

32

输入 #2复制

7
1 5 14 18 20 28 31 34 39 42

输出 #2复制

21

说明/提示

样例一说明：

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

注意：

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

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

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

赛后强化版于2020年10月13日19点18分已强化完毕。

 解析：背包

性质1：对于总重为x的赛斯石我们发现它可以通过载重为 y，z 的船进行运输

性质2： 一艘船可以运多种不同重量的赛斯石，如载重为5 的船可以运输重量为2 和3 赛斯的赛斯石（我最开始就忽略了这点）

根据以上两点性质可以对集合进行状态的划分，不过这里需要进行两次dp，第一次先算出每艘船的最大收益，再dp出每个重量对应的最大收益，可以看看这个方法是否行的通。

对船的收益进行dp：
 a[i] 表示重量为 i 的船的最大收益+w[i]，易知，这是一个不重不漏的划分方式

状态下转移方程为：a[i]=max( a[i-j]+v[j] , a[i] );

当然，最后还需要 a[i]-=w[i];

对重量对应的最大收益进行dp：

f[i] 表示重量为 i 的赛斯石的最大收益，易知，这也是个不重不漏的划分

状态转移方程：f[i]= max ( f[i-j]+a[j] , f[i] );

#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<math.h>
#include<map>
#include<unordered_map>
using namespace std;
typedef long long LL;
const int N = 1e5 + 5, M = 1e3 + 5;
int  w[12] = {0,1,3,5,7,9,10,11,14,15,17 };
int n;
LL v[12], f[N],a[20];int main() {cin >> n;for (int i = 1; i <= 10; i++) {scanf("%lld", &v[i]);}for (int i = 1; i <= 10; i++) {for (int j = 1; j <= i; j++) {a[i] = max(a[i], a[i - j] + v[j]);}}for (int i = 1; i <= 10; i++) {a[i] -= w[i];}for (int i = 1; i <= n; i++) {for (int j = 1; j <= min(i,10); j++) {f[i] = max(f[i], f[i - j]+a[j]);}}cout << f[n] << endl;return 0;
}