P12214 [蓝桥杯 2023 国 Python B] 贸易航线

题目描述

小蓝要带领一支船队依次经过 $n$ 个地点。小蓝的船上可以携带 $k$ 单位的商品，商品共有 $m$ 种，在每个地点的价格各不相同，部分商品在部分地区无法交易。

一开始小蓝的船是空的，小蓝可以在每个地点任意地买入各种商品，然后在之后经过的地点卖出。小蓝的钱很多，你可以认为小蓝买入商品时只会受到船队的容量的限制。

问小蓝到达终点时的最大收益是多少。

输入格式

输入的第一行包含三个整数 $n,m,k$，相邻的整数之间使用一个空格分隔。

接下来 $n$ 行，每行包含 $m$ 个整数，其中第 $i$ 行的第 $j$ 个数 $P_{i,j}$ 表示在第 $i$ 个地点第 $j$ 种商品的价格。特别地，值为 $-1$ 表示该商品在这个地区无法交易。

输出格式

输出一行包含一个整数表示答案。

输入输出样例 #1

输入 #1

7 4 4
1 2 3 6
-1 2 3 4
-1 2 4 4
3 3 2 2
2 5 3 1
1 3 3 2
1 2 4 2

输出 #1

24

说明/提示

评测用例规模与约定

• 对于 $20\%$ 的评测用例，$n\le 300$，$m\le 3$，$k\le 10$；
• 对于 $40\%$ 的评测用例，$n\le 2000$，$m\le 4$，$k\le 50$；
• 对于所有评测用例，$1\le n\le 10^5$，$1\le m\le 10$，$1\le k\le 100$，$1\le P_{i,j}\le 10^9$。

C++实现

#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;
}

后续：

接下来我会不断用C++来实现信奥比赛中的算法题、C++考级编程题实现、白名单赛事考题实现，感兴趣的请关注，我后续将继续分享相关内容