题意理解
有 NNN 赛斯重量的石头，可以切割成若干块（每块 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]maxIncome[w]maxIncome[w] 表示：用一艘载重为 www 的船，装满 www 重量的石头（最优切割），能获得的最大收入。
这是一个完全背包问题：
maxIncome[w]=maxi=1w(maxIncome[w−i]+a[i])maxIncome[w] = \max_{i=1}^{w}(maxIncome[w-i] + a[i]) maxIncome[w]=i=1maxw (maxIncome[w−i]+a[i])
然后计算净盈利：profit[w]=maxIncome[w]−cost[w]profit[w] = maxIncome[w] - cost[w]profit[w]=maxIncome[w]−cost[w]
第二步：分配总重量到各艘船
设 dp[j]dp[j]dp[j] 表示：运送 jjj 重量石头的最大盈利。
这又是一个完全背包问题：
dp[j]=maxw=1min(10,j)(dp[j−w]+profit[w])dp[j] = \max_{w=1}^{\min(10,j)}(dp[j-w] + profit[w]) dp[j]=w=1maxmin(10,j) (dp[j−w]+profit[w])
边界条件：
* maxIncome[0]=0maxIncome[0] = 0maxIncome[0]=0，dp[0]=0dp[0] = 0dp[0]=0
答案： dp[N]dp[N]dp[N]
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
参考代码
