T2-17 赛斯石

题意理解

有 $N$ 赛斯重量的石头，可以切割成若干块（每块 1-10 si），每块售价由输入给出。需要用船运输，船有 10 种载重（1-10 si），船费固定。一艘船可以装多块石头，只要总重量不超过载重。求最大总盈利（总收入 - 总船费）。

船费表：

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

---

思路分析

问题可以分解为两步：

第一步：预处理每种载重船的最优方案

设 $maxIncome[w]$ 表示：用一艘载重为 $w$ 的船，装满 $w$ 重量的石头（最优切割），能获得的最大收入。

这是一个完全背包问题：

$$maxIncome[w] = \max_{i=1}^{w}(maxIncome[w-i] + a[i])$$

然后计算净盈利：$profit[w] = maxIncome[w] - cost[w]$

第二步：分配总重量到各艘船

设 $dp[j]$ 表示：运送 $j$ 重量石头的最大盈利。

这又是一个完全背包问题：

$$dp[j] = \max_{w=1}^{\min(10,j)}(dp[j-w] + profit[w])$$

边界条件：

• $maxIncome[0] = 0$，$dp[0] = 0$

答案： $dp[N]$

---

参考代码

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;  // 最大重量

int N;             // 总重量
int a[15];         // 每种重量石头的售价
int cost[15] = {0, 1, 3, 5, 7, 9, 10, 11, 14, 15, 17};  // 船费（下标1-10）
int maxIncome[15]; // maxIncome[w]表示装满w重量的船能获得的最大收入
int profit[15];    // profit[w]表示用一艘载重w的船的净盈利
int dp[MAXN];      // dp[j]表示运送j重量石头的最大盈利

int main() {
    cin >> N;  // 读入总重量
    
    for (int i = 1; i <= 10; i++) {  // 读入每种重量的售价
        cin >> a[i];
    }
    
    // 第一步：计算maxIncome[w]，用完全背包
    maxIncome[0] = 0;  // 边界：0重量收入为0
    for (int w = 1; w <= 10; w++) {  // 枚举载重
        maxIncome[w] = 0;
        for (int i = 1; i <= w; i++) {  // 枚举最后一块石头的重量
            maxIncome[w] = max(maxIncome[w], maxIncome[w - i] + a[i]);
        }
    }
    
    // 第二步：计算每种载重船的净盈利
    for (int w = 1; w <= 10; w++) {
        profit[w] = maxIncome[w] - cost[w];
    }
    
    // 第三步：完全背包，计算总重量N的最大盈利
    dp[0] = 0;  // 边界：0重量盈利为0
    for (int j = 1; j <= N; j++) {  // 枚举总重量
        dp[j] = -0x3f3f3f3f;  // 初始化为负无穷
        for (int w = 1; w <= 10 && w <= j; w++) {  // 枚举这艘船的载重
            dp[j] = max(dp[j], dp[j - w] + profit[w]);  // 状态转移
        }
    }
    
    cout << dp[N] << endl;  // 输出答案
    return 0;
}