题解：AtCoder AT_awc0001_d Merchant on the Highway

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。

欢迎大家订阅我的专栏：算法题解：C++与Python实现！

附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总

【题目来源】

AtCoder：D - Merchant on the Highway

【题目描述】

Takahashi is a merchant doing business along a highway that extends from east to west. There areN NNtowns lined up in a row along this highway, numbered1 , 2 , . . . , N 1, 2, ..., N1,2,...,Nfrom west to east. Doing business in thei ii-th town yields a profit ofA i A_iAi​, but costsB i B_iBi​yen as accommodation expenses.
高桥是一位沿着东西向高速公路经商的商人。这条公路上有一排N NN个城镇，自西向东编号为1 , 2 , . . . , N 1, 2, ..., N1,2,...,N。在第i ii个城镇经商可获得A i A_iAi​的利润，但需要花费B i B_iBi​日元作为住宿费用。

Takahashi has decided to select some of these towns to do business in. However, Takahashi’s carriage has the following restriction:
高桥决定从这些城镇中选择一部分进行经商。然而，高桥的马车有以下限制：

• The towns visited do not need to have consecutive numbers, but when the visited town numbers are arranged in ascending order, the difference between any two adjacent numbers must be at mostK KK. In other words, if the visited town numbers in ascending order arep 1 , p 2 , … , p m p_1,p_2,…,p_mp1​,p2​,…,pm​, thenp j + 1 − p j ≤ K p_{j+1}−p_j≤Kpj+1​−pj​≤Kmust hold for all1 ≤ j ≤ m − 1 1≤j≤m−11≤j≤m−1. This is because the carriage has a limit on the distance it can travel at once.
  访问的城镇编号无需连续，但当按升序排列访问的城镇编号时，任意两个相邻编号之差必须至多为K KK。换言之，如果按升序排列的访问城镇编号为p 1 , p 2 , … , p m p_1, p_2, …, p_mp1​,p2​,…,pm​，则对于所有1 ≤ j ≤ m − 1 1 ≤ j ≤ m-11≤j≤m−1，必须满足p j + 1 − p j ≤ K p_{j+1} - p_j ≤ Kpj+1​−pj​≤K。这是因为马车单次可行驶的距离有限制。

The total accommodation expenses Takahashi can prepare isM MMyen. When selecting towns such that the total accommodation expenses of visited towns is at mostM MMyen, find the maximum possible total profit.
高桥能够准备的住宿费用总额为M MM日元。在满足访问城镇的总住宿费用不超过M MM日元的条件下选择城镇时，求可能的最大总利润。

Note that if no town is visited, the total profit is0 00.
注意，如果未访问任何城镇，总利润为0 00。

【输入】

N NNM MMK KK

A 1 A_1A1​B 1 B_1B1​

A 2 A_2A2​B 2 B_2B2​

⋮ \vdots⋮

A N A_NAN​B N B_NBN​

• The first line containsN NNrepresenting the number of towns,M MMrepresenting the total accommodation expenses available, andK KKrepresenting the maximum number of towns that can be traveled at once, separated by spaces.
• From the 2nd line to the( N + 1 ) (N+1)(N+1)-th line, information about each town is given.
• The( 1 + i ) (1+i)(1+i)-th line contains the profitA i A_iAi​obtainable in thei ii-th town and the accommodation expenseB i B_iBi​, separated by spaces.

【输出】

Output in one line the maximum possible total profit when selecting towns that satisfy the conditions.

【输入样例】

5 10 2 8 3 5 4 10 5 3 2 7 3

【输出样例】

21

【解题思路】

【算法标签】

#01背包#

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongconstintN=205;intn,m,k,ans;// n: 物品数量，m: 预算，k: 允许的最大物品间隔，ans: 最大总价值intdp[N][N][N];// 动态规划数组 dp[考虑了前i个物品][使用了j的钱][最后一个购买的物品编号是p] = 最大总价值structNode{intid,A,B;// id: 物品编号，A: 物品价值，B: 物品价格}a[N];signedmain(){cin>>n>>m>>k;// 读入物品数量、预算、最大间隔限制for(inti=1;i<=n;i++){cin>>a[i].A>>a[i].B;// 读入物品的价值和价格a[i].id=i;// 记录物品编号}// 动态规划求解for(inti=1;i<=n;i++)// 逐个考虑每个物品{for(intj=0;j<=m;j++)// 枚举使用的预算{for(intp=0;p<=n;p++)// 枚举最后一个购买的物品编号{// 不购买当前第i个物品dp[i][j][p]=max(dp[i][j][p],dp[i-1][j][p]);// 购买当前第i个物品的条件：// 1. 预算足够 (j >= a[i].B)// 2. 与上一个购买物品的间隔不超过k (a[i].id - a[p].id <= k)// 注意：当p=0时，a[0].id未定义，但a[i].id - 0 <= k 总是成立if(j>=a[i].B&&a[i].id-a[p].id<=k){// 状态转移：从dp[i-1][j-a[i].B][p]转移而来// 表示前i-1个物品花费j-a[i].B，最后一个购买的是物品p// 然后购买当前第i个物品，最后一个购买的物品变为idp[i][j][i]=max(dp[i][j][i],dp[i-1][j-a[i].B][p]+a[i].A);}}}}// 在所有状态中寻找最大总价值for(intj=0;j<=m;j++)// 枚举所有可能的预算使用情况{for(intp=0;p<=n;p++)// 枚举最后一个购买物品的所有可能{ans=max(ans,dp[n][j][p]);// 取最大值}}cout<<ans<<endl;// 输出答案return0;}

【运行结果】

5 10 2 8 3 5 4 10 5 3 2 7 3 21