塞斯石

惠存xs · 2022-07-25 08:35:21 · 题解

P3983 赛斯石

赛斯石（赛后强化版）

题目描述

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

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

思路

• 这题如果从石头出发来考虑，会发现船会很难处理。因此换个角度思考，可以看出每个船的最大收益是容易计算的。所以我们可以先处理出每艘船的最大收益（一个完全背包），最后只需求出怎样租船收益最高即为答案（将船的最大收益看作价值，所载石头的质量即为代价，依旧是一个完全背包）。
• 因为不同质量的石头的价值都为正数，所以要想船的收益最大，那必然要使船装满，因此每艘船的代价即为能承载石头的最大质量。

附上代码

#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;
}

蒟蒻的第一篇题解，有什么错误还请各位大佬指出