P3983 赛斯石（赛后加强版）踢姐

简要题意

题目链接

商家手里有 \(si\) 个重量为 \(1\) 的赛斯石，每两个塞斯石可以合并为一个重量更大的塞斯石，最大重量不能超过 \(10\) ，合并得到的塞斯石的重量为先前两个塞斯石的重量总和，每种重量的塞斯石售价不同，现在一共有 \(10\) 种载重不同的船，每艘船的租金和载重分别为：

载重	1	2	3	4	5	6	7	8	9	10
租金	1	3	5	7	9	10	11	14	15	17

商家要先将塞斯石进行处理合并（也可以不合并）完，然后将处理好的塞斯石运到河对岸售卖，之后不可再对塞斯石进行处理，现在求商家最大盈利（盈利=塞斯石售价总和-租船费用总和）

思路分析

没仔细研究样例的我看到这题以为就是简单背包，故搓了不知道能得多少分但是指定满江红的一般背包：

for(i=1;i<=s;++i){for(j=1;j<=min(10,i);++j){if(i-j>=0){dp[i]=max(dp[i-j]+c[j]-w[j],dp[i]);}}
}

于是样例错了，让我们看看这个样例：

7
1 5 14 18 20 28 31 34 39 42

根据我的一番手玩（实则是翻了讨论区）之后得知，这题的最优解应该是租一条可以载重 \(7\) 重量的船，并将所有的塞斯石合并为两块重量分别为 \(3\) 和 \(4\) 的塞斯石运走，原来如此！

那么这题的关键在于一艘船可以装多个塞斯石，比如一艘载重为 \(7\) 的船可以单独装载重量 \(7\) 的塞斯石，也可以装两块重量分别为 \(3\) 和 \(4\) 的塞斯石，我们原先的转移很显然是单块单块的转移，可现在题目存在一条船装多块怎么办？

此时我们的状态设计为 \(dp_i\) 为装载重量为 \(i\) 的塞斯石的最大收益，之前的转移就是一艘船一块塞斯石，现在由于一艘船可以装很多块，我们的问题转化为了对于我们租用的每一艘船带来的总利益最大化，此时装载的塞斯石总重量是不变的，我们考虑如何安排每一块塞斯石的重量

我们知道一块整块的塞斯石无法同时被两条船装载（废话），如果两艘船各自的空余都装不下这块塞斯石，那么必须拆分为两块放入两艘船，所以自然不存在前一条船装载了某块塞斯石而影响后续船只的装载，举个例子：

第一条船：载重7，空余7
第二条船：载重6，空余6
此时向第一条船中放入一块重量为5的塞斯石
第一条船：载重7，空余2
第二条船：载重6，空余6
此时向第二条船中放入一块重量为5的塞斯石
第一条船：载重7，空余2
第二条船：载重6，空余1

此时若要再放入重量为 \(3\) 的塞斯石，则只能将这块塞斯石拆分，分别放入两条船中，那么这一整块的塞斯石的价格便会被拆分为 \(2\) 和 \(1\) 的价格，所以不会存在前一艘船的放置影响后续的放置。

所以我们得出如下性质：每艘船的决策都是互相独立的，故每一艘装载重量不同的船都有独立且不会被其他船只影响的最优解

现在就很明朗了，我们可以先求每种重量的船可以存储的最大价值塞斯石的价值，然后就变成了如何选船使得总收益最大，问题便从绿dp转化为了两个橙背包dp，这题就结束了。

代码思路

我们先对每一艘船的最大价值求解，我们计载重为 \(i\) 的船可以获得的最大价值为 \(v_i\) ，先求出对于所有 \(v_i|1\le i \le 10\) 的值，然后就进行完全背包即可。

核心🐎

for(i=1;i<=10;++i){for(j=1;j<=i;++j){v[i]=max(v[i],v[i-j]+c[j]);}
}
for(i=1;i<=s;++i){for(j=1;j<=min(10,i);++j){dp[i]=max(dp[i],dp[i-j]+v[j]-w[j]);}
}