题解：P12214 [蓝桥杯 2023 国 Python B] 贸易航线
Deakin
·
·
题解
闲话
dalao 们都已经说的很好了，我就补充几点。
- 一定要开
long long。（血的教训）
- 一定要记得用记忆化搜索。（血的教训 2）
- 卖完之后可以立即买入。
动态规划
### 动态规划转移：
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$。
## 完整代码
```cpp
#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记录](https://www.luogu.com.cn/record/217088807)。点个赞再走呗 QAQ，求通过。