自动搬运

查看原文

来自洛谷，原作者为

	Deakin 你好 (^w^)/

搬运于2025-08-24 23:13:45，当前版本为作者最后更新于2025-05-14 00:46:42，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

闲话

dalao 们都已经说的很好了，我就补充几点。

1. 一定要开 long long。（血的教训）
2. 一定要记得用记忆化搜索。（血的教训 2）
3. 卖完之后可以立即买入。

动态规划

$dp[x][y]‌$：表示在第 $x$ 个地点，当前持有商品 $y$（$y=0$ 表示空仓）时，每单位商品的最大收益。

动态规划转移‌：

1. 买入：遍历所有可买入的商品，选择未来收益最大的。
2. 若持有商品 $y$，可选择卖出。特别的，卖出后能立即买入。
3. 保持‌：不进行任何操作，直接前往下一地点。

状态转移方程：

$$dp[x][y] = \max \begin{cases} \displaystyle \max_{\substack{1 \leq i \leq m \\ P[x][i] \neq -1}} \Big( dp[x+1][i] - P[x][i] \Big) & y = 0 \\ \max \Big( dp[x+1][y],\ \Big( dp[x][0] + P[x][y] \Big) \Big) & y > 0 \ \text{且} \ P[x][y] \neq -1 \\ dp[x+1][y] \end{cases} $$

关键：

为什么不同时买多种商品： 假设同时买入多种商品比单一商品更优，则存在某一种商品利润更高，与假设矛盾。

为什么满载交易（买入卖出单位为 $k$）： 若非满载交易则必然有剩余空间，造成了浪费，不是最优解。

既然已经证明每次交易的单位为 $k$ 时最优。那我们假设 $k=1$ 通过动态规划求解答案，最后答案再乘 $k$ 不就行了。 最终总收益为 $dp[1][0] \times k$。

完整代码

#include<iostream>
using namespace std;
int n,m,k;
int P[100001][11];
long long dp[100001][11],b[100001][11];
long long dfs(int x,int y){
    if(x>n)return 0;
    if(b[x][y]==1)return dp[x][y];//记忆化
    b[x][y]=1;
    long long ans=0;
    if(y==0){
        for(int i=1;i<=m;i++){
            if(P[x][i]!=-1)ans=max(ans,dfs(x+1,i)-P[x][i]);//买入商品
        }
    }else if(P[x][y]!=-1)ans=dfs(x,0)+P[x][y];//卖出商品+腾出的位置再次买入
    dp[x][y]=max(ans,dfs(x+1,y));//不卖也不买
    return dp[x][y];
}
int main(){
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++)scanf("%d",&P[i][j]);
    }
    printf("%lld",dfs(1,0)*k);
    return 0;
}

AC记录。点个赞再走呗 QAQ，求通过。