洛谷P3983 赛斯石（赛后强化版）题解

题意：

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

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

输入格式：

输入一共有两行

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

第二行有十个数据 $a_1,a_2,\dots, a_{10}$（分别为 $1\mathtt{si}$ 到 $10\mathtt{si}$ 的赛斯石市场价格，单位：元）

输出格式：

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

数据范围：

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

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

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

值得注意的是，每艘载重为 $k$ 的船并非只能装一块重 $k$ 的

所以我们还要预处理出载重为 $k$ 的船能获得的最大收益

设 $b_i$ 表示使用载重为 $i$ 的船所得收益的最大值，则

$b_i = \max\left\{a_i,~\max_{1\le j < i} \{b_{i-j} + b_j\}\right\}-c_i$

其中 $c_i$ 表示租这个船的价格，就是上面表里的价格。

然后就是朴素的完全背包啦！

设 $f_{i,j}$ 表示只考虑前 $i$ 种船，一共运了 $j \,\mathtt{si}$ 的石头的最大收益

$f_{i,j} = \max \left\{f_{i-1,j},~(f_{i,j-i} + b_i)\times [i \le j]\right\}$

最终的答案就是 $f_{10,n}$ ，然后滚一滚空间啥的。

时间复杂度 $O(nm)$

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cstdarg>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
namespace FastIO
{
    #define gc() readchar()
    #define pc(a) putchar(a)
    #define SIZ (int)(1e6+15)
    char buf1[SIZ],*p1,*p2;
    char readchar()
    {
        if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
        return p1==p2?EOF:*p1++;
    }
    template<typename T>void read(T &k)
    {
        char ch=gc();T x=0,f=1;
        while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
        while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
        k=x*f;
    }
    template<typename T>void write(T k)
    {
        if(k<0){k=-k;pc('-');}
        static T stk[66];T top=0;
        do{stk[top++]=k%10,k/=10;}while(k);
        while(top){pc(stk[--top]+'0');}
    }
}using namespace FastIO;
#define N ((int)(1e5+15))

int n,a[15],f[N];
const int c[11] = {0, 1, 3, 5, 7, 9, 10, 11, 14, 15, 17};
void up(int &x,int y){ x < y ? x=y : 0;}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
	cin >> n;
	for(int i=1; i<=10; i++) cin >> a[i];
	for(int i=2; i<=10; i++)
		for(int j=1; j<i; j++)
			up(a[i], a[i-j]+a[j]);
	for(int i=1; i<=10; i++) a[i]-=c[i];
	memset(f,0xc0,sizeof(f));
	f[0]=0;
	for(int i=1; i<=10; i++)
		for(int j=i; j<=n; j++)
			up(f[j], f[j-i]+a[i]);
	cout << f[n] << '\n';
    return 0;
}