P3983 赛斯石（赛后强化版）
题目背景
白露横江，水光接天，纵一苇之所如，凌万顷之茫然。——苏轼
真程海洋近来需要进购大批赛斯石，你或许会问，什么是赛斯石？
首先我们来了解一下赛斯，赛斯是一个重量单位，我们用$ si
作为其单位。比如
作为其单位。比如
作为其单位。比如 1
赛斯就是
赛斯就是
赛斯就是 1si $。
而赛斯石有这样一个性质，它本来是一赛斯一赛斯单独存在的，但是用自然枪将其精化之后，它就会与其它经过精化的赛斯石进行合并，合并到合适的重量之后，便将其钝化，使其不再合并其它赛斯石，如果合错了，也可以用金刚刀将其切开（神奇的是你只能切成整数赛斯重量）。赛斯石的重量只能是整数赛斯重量，而不同赛斯重量的赛斯石的价格也是不一样的。
题目描述
现需上市$ Need
赛斯重量的赛斯石，卖家想算出这些赛斯石经过某种合并方式来获得的最大收益。然而目前有一个问题，市场在真程大殿附近（真程海洋中心位置），卖家需要租船送赛斯石过去（即不考虑卖家自己租船过去的费用），目前有十种船可以租，载重量从
赛斯重量的赛斯石，卖家想算出这些赛斯石经过某种合并方式来获得的最大收益。然而目前有一个问题，市场在真程大殿附近（真程海洋中心位置），卖家需要租船送赛斯石过去（即不考虑卖家自己租船过去的费用），目前有十种船可以租，载重量从
赛斯重量的赛斯石，卖家想算出这些赛斯石经过某种合并方式来获得的最大收益。然而目前有一个问题，市场在真程大殿附近（真程海洋中心位置），卖家需要租船送赛斯石过去（即不考虑卖家自己租船过去的费用），目前有十种船可以租，载重量从 1si
到
到
到 10si $，每艘船的租价也是有所不同的，如下表所示：
由于真程大殿附近有强烈的赛斯力，导致无法对赛斯石进行任何操作，商家将赛斯石运过来之后就只能按照之前合并好的卖。假设卖家不返回，且这些赛斯石全部能卖出去。现在卖家他要计算总盈利（设总盈利=赛斯石的总收益-租船所需总费用），请你设计一个程序，算出一种最佳方案，以获得最大总盈利。
输入格式
输入一共有两行
第一行有一个数据$ Need
（赛斯石的总量，单位：
（赛斯石的总量，单位：
（赛斯石的总量，单位： si $）
第二行有十个数据$ a_{1}\\ …\\ a_{10}
（分别为
（分别为
（分别为 1si
到
到
到 10si $的赛斯石市场价格，单位：元）
输出格式
输出仅一行，包含一个整数，表示最大总盈利。
输入输出样例 #1
输入 #1
11
1 6 11 17 23 27 33 35 38 43
输出 #1
32
输入输出样例 #2
输入 #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 $分已强化完毕。
C++实现
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll f[20],n,m,a[20],v[20]={0,1,3,5,7,9,10,11,14,15,17};//v数组储存租每艘船的费用
ll dp[100010],ans;
int main()
{
scanf("%lld",&n);
for(int i=1;i<=10;i++) scanf("%lld",&a[i]);
for(int i=1;i<=10;i++)
for(int j=i;j<=10;j++)
f[j]=max(f[j–i]+a[i],f[j]);//计算每艘船的最大总收益
for(int i=1;i<=10;i++) f[i]=f[i]–v[i];//相减即为最大净收益
for(int i=1;i<=10;i++)
for(int j=i;j<=n;j++)
dp[j]=max(dp[j–i]+f[i],dp[j]);//计算答案
for(int i=1;i<=n;i++) ans=max(ans,dp[i]);
cout<<ans<<endl;
return 0;
}
后续
接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容
