题解 P3983 【赛斯石（赛后强化版）】
fanxingzhi
·
·
题解
思路
刚学完 01 背包、完全背包的同学，拿到这题肯定是懵的。
进来看题解后，发现更懵，虽然大牛的代码都很短，但好难理解啊。
背包题这么难吗，很受打击。
言归正传，往下看定会豁然开朗。
一看就是背包题，但怎么才能套入背包的模型里去：
前 i 种规格的石头卖出 j 重量，能实现的最大盈利？
很容易想到这个，但费用怎么处理？
这才是本题的关键，搞定这个问题，那就是一道基础背包题。
看船费数据，不同规格的石头找到对应载重的船运走似乎不是最优的选择，似乎有些石头可以选择拼船会更省钱。
于是我们想，如果题目规定石头只能自己一个石头单独乘坐一条船，不能拼船，那就好了。
直接把不同规格的石头的价值减去对应的船费就是盈利了，
然后递推前 i 种规格的石头，卖出 j 重量能实现的最大盈利，轻松搞定。
但是题目并没有这样规定。
不过，我们惊喜地发现，除了少量几个规格的石头存在拼船更便宜，大部分都是自己一块石头一条船就是最省钱的啦。
大胆设想：能否自己新创几个规格出来，题目里只有 10 种规格的石头，重量分别是 1-10，价值也各有不同。
那我们把拼船更便宜的那个几个石头进行打包，整出几个新的规格：
$3$ 和 $4$ 搞组合，变成第 $12$ 号规格的石头，重量为 $7$，价值自己去算。
$4$ 和 $5$ 搞组合，变成第 $13$ 号规格的石头，重量为 $9$，价值自己去算。
$5$ 和 $5$ 搞组合，变成第 $14$ 号规格的石头，重量为 $10$，价值自己去算。
看到这里应该会了吧；递推前 $i$ 种规格的石头，卖出 $j$ 重量能实现的最大盈利，记得每个规格的石头的盈利要先减去对应的船费。
以样例 $2$ 为例，人脑运行一下：
当运行到前 $7$ 个规格的时候，$dp[n]$ 等于 $20$ (因为选择 $7$ 号规格就是最大盈利，当然 $3$ 和 $4$ 的组合也是 $20$）。
再运行到前 $11$ 个规格的时候，$dp[n]$ 不会有变化，因为 $2$ 号规格和 $5$ 号规格的石头价值之和减去 $7$ 号船的费用还是不超过 $20$。虽然省了 $1$ 块钱运费，但因为他们本身的价值不够高，省的一块钱没起到作用。
再运行到前 $12$ 个规格的时候，因为 $3$ 号规格和 $4$ 号规格的石头价值之和减去 $7$ 号船的费用是 $21$，超过了原来的最高值，省下的那一块钱起到了决定性作用。
这就是新创几个新规格的作用了。当他们几个单独坐船的盈利之和能跟别人打成平手（从给定的船费看，拼船最多也就剩 $1$ 块钱）的时候，他们就可以通过拼船省下钱，从而可能影响到最终的选择。
看到这里应该没必要再往下看了吧，不过还是整上代码吧，毕竟是第一次写题解：
**代码**
```c
#include <iostream>
using namespace std;
int fy[11]={0,1,3,5,7,9,10,11,14,15,17}; //不同载重量船的费用。
int val[21]; //不同规格的石头的价值。
int w[21]; //不同规格的石头的重量。
int n;
long long dp[100005];
int main()
{
cin>>n;
for(int i=1;i<=10;i++)
{
cin>>val[i]; //输入 10 种不同规格的石头的价值（没减船费前）
w[i]=i; //把 10 种不同规格的石头的重量数据存入 w 数组。
}
//手打记录 4 种新规格石头的重量及价值（同时操作减船费，价值变成了盈利）。
w[11]=2+5; val[11]=val[2]+val[5]-fy[7];
w[12]=3+4; val[12]=val[3]+val[4]-fy[7];
w[13]=4+5; val[13]=val[4]+val[5]-fy[9];
w[14]=5+5; val[14]=val[5]+val[5]-fy[10];
for(int i=1;i<=10;i++)
val[i]=val[i]-fy[i];
//前 10 种规格的石头的价值减去船费，变成盈利。
for(int i=1;i<=14;i++)
for(int j=w[i];j<=n;j++)
dp[j]=max(dp[j],dp[j-w[i]]+val[i]);
cout<<dp[n];
return 0;
}
```