弘泽建设集团网站,求职招聘网站开发,企业网站网络推广怎么做,怎么做网站dns加速题目背景
白露横江#xff0c;水光接天#xff0c;纵一苇之所如#xff0c;凌万顷之茫然。——苏轼真程海洋近来需要进购大批赛斯石#xff0c;你或许会问#xff0c;什么是赛斯石#xff1f;
首先我们来了解一下赛斯#xff0c;赛斯是一个重量单位#xff0c;我们用…题目背景
白露横江水光接天纵一苇之所如凌万顷之茫然。——苏轼真程海洋近来需要进购大批赛斯石你或许会问什么是赛斯石
首先我们来了解一下赛斯赛斯是一个重量单位我们用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的赛斯石我们发现它可以通过载重为 yz 的船进行运输
性质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] );
#includeiostream
#includestring
#includecstring
#includecmath
#includectime
#includealgorithm
#includeutility
#includestack
#includequeue
#includevector
#includeset
#includemath.h
#includemap
#includeunordered_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;
}
