思路

为了最大化行走的距离，直观的想法是尽量积累更多的增强，使得每天能行走的步数达到最大。然而，获得增强会导致当天的行走步数减少，因此不能直接贪心地获取所有增强。为此，我们使用动态规划来求解。

令状态 $dp[i][j]$ 表示在前 $i$ 天到达坐标 $j$ 时，所能积累的最大步数。对于每个坐标 $j$，如果存在多个增强，则选择其中最大的增强是最优的策略。因此，状态转移方程为：

$dp[i][j] = \max \{ \text{所有能到达} j \text{点的增强} \} + \text{当前位置的最大增强值（若无增强则为 0）}$

最终答案的求解公式为：

$\text{ans} = \max \left\{ j + dp[i][j] \times (t - i) \right\}$

即第 $i$ 天到达坐标 $j$ 时，考虑之后每天以 $dp[i][j]$ 的步数行走时，能够获得的最大距离。

代码

python

from collections import defaultdict
T=int(input())
for i in range(T):
    K,t,N=map(int,input().split())
    x=list(map(int,input().split()))
    y=list(map(int,input().split()))
    mp=defaultdict(int)
    for i in range(len(x)):
        mp[x[i]]=max(mp[x[i]],y[i])
    dp=[[-1]*51 for i in range(t+1)]
    dp[0][0]=K
    for i in range(1,t+1):
        for j in range(51):
            dp[i][j]=dp[i-1][j]
            for k in range(0,j):
                if dp[i-1][k]!=-1 and dp[i-1][k]+k>=j:
                    dp[i][j]=max(dp[i][j],dp[i-1][k]+mp[j])
    ans=0
    for i in range(1,t+1):
        for j in range(51):
            if dp[i][j]!=-1:
                ans=max(ans,j+dp[i][j]*(t-i))
    print(ans)

java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();

        for (int test = 0; test < T; test++) {
            int K = sc.nextInt();
            int t = sc.nextInt();
            int N = sc.nextInt();

            int[] x = new int[N];
            int[] y = new int[N];

            for (int i = 0; i < N; i++) {
                x[i] = sc.nextInt();
            }

            for (int i = 0; i < N; i++) {
                y[i] = sc.nextInt();
            }

            Map<Integer, Integer> mp = new HashMap<>();
            for (int i = 0; i < N; i++) {
                mp.put(x[i], Math.max(mp.getOrDefault(x[i], 0), y[i]));
            }

            int[][] dp = new int[t + 1][51];
            for (int[] row : dp) {
                Arrays.fill(row, -1);
            }
            dp[0][0] = K;

            for (int i = 1; i <= t; i++) {
                for (int j = 0; j < 51; j++) {
                    dp[i][j] = dp[i - 1][j];
                    for (int k = 0; k < j; k++) {
                        if (dp[i - 1][k] != -1 && dp[i - 1][k] + k >= j) {
                            dp[i][j] = Math.max(dp[i][j], dp[i - 1][k] + mp.getOrDefault(j, 0));
                        }
                    }
                }
            }

            int ans = 0;
            for (int i = 1; i <= t; i++) {
                for (int j = 0; j < 51; j++) {
                    if (dp[i][j] != -1) {
                        ans = Math.max(ans, j + dp[i][j] * (t - i));
                    }
                }
            }

            System.out.println(ans);
        }

        sc.close();
    }
}

c++

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <cstring>
using namespace std;

int main() {
    int T;
    cin >> T;

    while (T--) {
        int K, t, N;
        cin >> K >> t >> N;

        vector<int> x(N), y(N);
        for (int i = 0; i < N; i++) {
            cin >> x[i];
        }

        for (int i = 0; i < N; i++) {
            cin >> y[i];
        }

        map<int, int> mp;
        for (int i = 0; i < N; i++) {
            mp[x[i]] = max(mp[x[i]], y[i]);
        }

        vector<vector<int>> dp(t + 1, vector<int>(51, -1));
        dp[0][0] = K;

        for (int i = 1; i <= t; i++) {
            for (int j = 0; j < 51; j++) {
                dp[i][j] = dp[i - 1][j];
                for (int k = 0; k < j; k++) {
                    if (dp[i - 1][k] != -1 && dp[i - 1][k] + k >= j) {
                        dp[i][j] = max(dp[i][j], dp[i - 1][k] + mp[j]);
                    }
                }
            }
        }

        int ans = 0;
        for (int i = 1; i <= t; i++) {
            for (int j = 0; j < 51; j++) {
                if (dp[i][j] != -1) {
                    ans = max(ans, j + dp[i][j] * (t - i));
                }
            }
        }

        cout << ans << endl;
    }

    return 0;
}

题目内容

小塔正在游戏中进行一次有趣的探险，他第$0$天结束后在起点$0$位置，要安排接下来$1$~$t$天的行程、初始时每天最多可以选择前进$K$格。

沿途有一些特定的位置$x[i]$，在这些位置上小塔可以选择停下来获取增强，并且今天不再继续行进，可以使得之后每天能多行走$y[i]$格(也可以途径时不停下，选择继续进行今日的行程，但不会获得增强)。

一个位置可能有多个增强，小塔只能选择其中一个获得，即使再多停留一天也不能获得其他的增强效果。

小塔想知道在$t$天后，他最多能走到哪一位置。

输入描述

第一行$1$个整数$T$，表示数据组数。

对于每组数据:

第一行包含三个整数$K$、$t$和$N$，分别表示初始每天最多前进的格数、总天数以及可以获得增强的位置的数量。

第二行包含$N$个整数$x[1],x[2],...,x[N]$。

第三行包含$N$个整数$y[1],y[2],...,y[N]$。

其中$x[i],y[i]$分别是第$i$个可以获得增强的位置以及增强的强度。

$1≤T≤5,0≤t≤100,1≤N≤50,1≤x[i],y[i],K≤50$

输出描述

输出$T$行分别表示每组数据答案。

对每组数据，输出一行一个整数，表示在$t$天后，小塔能够到达的最远位置。

样例1

输入

2
3 5 2
2 5
2 1
1 0 1
1
1

输出

23
0

提示

对于第一组样例:

初始状态下，小塔每天可以前进最多$'3'$格。

第一天，小塔前进到$'2'$位置，接着停在$'2'$位置获取$'2'$格增强，使得他之后每天最多可以前进$'5'$格。

第二天，小塔前进到$'5'$位置，停在那获得$'1'$格增强，之后他每天最多行进$'6'$格。

第$3、4、5$天小塔均全速行进，每天前进$6$格。

在$'T=5'$天后，小塔可以利用增强前进到$'23'$位置。

对于第二组样例:

小塔的角色索性不走了，只走$0$天，由题面，他第$0$天结束后的位置就是位置$0$，所以答案就是$0$。