一个徒步旅行者计划穿越山脉进行多天的远足。有n条小径，每条小径都有一定的长度，以列表形式给出，需要按照列表中给出的顺序依次穿越。该徒步旅行者希望通过在最少的天数内完成这次远足，创造新的世界纪录。他还希望确保每天至少穿越一条小径，并确保每天穿越的最长小径长度之和尽可能地小。请找出这个最小的长度之和。
例如，假设有n = 6条小径，长度分别为trails = [10, 5, 9, 3, 8, 15]，记录record = 2。那么，徒步旅行者在第一天穿越第一条小径，因此最长的小径长度为10，在第二天穿越其余的小径，所以第二天的最长小径长度为max(5, 9, 3, 8, 15) = 15。所有天数中最长小径的长度之和为10 + 15 = 25。返回25。
其他例子：
**限制条件：**
n的大小为1到300，记录的大小为1到300，数组元素的值范围为1到10^5。 程序的结果是一个整数，所以不需要使用长整型。
这是我的方法：
从数组中选择前(record-1)个项目并将它们加入结果，然后从(record到数组长度)中获取最大的项目并将其加入结果。
根据指示我编写了代码。这是在一个月前的hackerrank面试中被问到的问题，这段代码只解决了15个测试用例中的10个。剩下的测试用例失败，显示输出错误，并且它们是隐藏的测试用例。
我是否漏掉了什么导致测试用例失败？我尝试使用长整型变量，但得分没有改善。
**更新：**
使用动态规划：
我尝试了Cary Swoveland提供的解决方案，但我不清楚我哪里出错了，我得到了错误的输出。
对于输入
例如，假设有n = 6条小径，长度分别为trails = [10, 5, 9, 3, 8, 15]，记录record = 2。那么，徒步旅行者在第一天穿越第一条小径，因此最长的小径长度为10，在第二天穿越其余的小径，所以第二天的最长小径长度为max(5, 9, 3, 8, 15) = 15。所有天数中最长小径的长度之和为10 + 15 = 25。返回25。
其他例子：
array = [150, 200, 400, 350, 250] and record = 3
Ans:
Cover the first trail on day 1, the second on day 2, and the remaining on day 3.
The total is 150 + 200 + max(400, 350, 250) = 750
例子：
array = [78, 45, 12, 56, 85, 45], record=1
Ans:
Covers all the trails in one day.
Output = 85
**限制条件：**
n的大小为1到300，记录的大小为1到300，数组元素的值范围为1到10^5。 程序的结果是一个整数，所以不需要使用长整型。
这是我的方法：
从数组中选择前(record-1)个项目并将它们加入结果，然后从(record到数组长度)中获取最大的项目并将其加入结果。
根据指示我编写了代码。这是在一个月前的hackerrank面试中被问到的问题，这段代码只解决了15个测试用例中的10个。剩下的测试用例失败，显示输出错误，并且它们是隐藏的测试用例。
我是否漏掉了什么导致测试用例失败？我尝试使用长整型变量，但得分没有改善。
**更新：**
使用动态规划：
public static void main(String[] args) {
solve(new int[]{1000, 500, 2000, 8000, 1500}, 3); // correct result : 9500
solve(new int[]{3000, 1000, 4000}, 2); // correct result : 7000
solve(new int[]{190, 200, 450, 499, 358, 160}, 3); // correct result : 849
}
public static void solve(int[] x, int D) {
int T = x.length; // Number of trails
int[][][] v = new int[T + 1][D + 1][T + 1];
int[][][] z = new int[T + 1][D + 1][T + 1];
// Dynamic programming
for (int t = 1; t <= T; t++) {
for (int d = 1; d <= Math.min(D, t); d++) {
for (int n = 1; n <= t; n++) {
if (t == 1 && d == 1) {
v[t][d][n] = x[t - 1];
z[t][d][n] = x[t - 1];
} else {
x[t - 1] = x[t - 1]; // Length of current trail
if (d == 1) {
z[t][d][n] = Math.max(z[t - 1][d][n - 1], x[t-1]);
v[t][d][n] = v[t - 1][d][n - 1] - z[t - 1][d][n - 1] + z[t][d][n];
} else {
int maxLastTrail = Math.max(z[t - 1][d][n - 1], x[t-1]);
z[t][d][n] = maxLastTrail;
v[t][d][n] = v[t - 1][d][n - 1] - z[t - 1][d][n - 1] + z[t][d][n];
}
}
}
}
}
// Finding the optimal value
int optimalValue = Integer.MAX_VALUE;
for (int n = 1; n <= T; n++) {
optimalValue = Math.min(optimalValue, v[T][D][n]);
}
//System.out.println("Optimal value: " + optimalValue);
// Backtracking to construct optimal solution
int daysLeft = D;
int trailsLeft = T;
int lastTrails = -1;
for (int n = T; n >= 1; n--) {
if (v[trailsLeft][daysLeft][n] == optimalValue) {
lastTrails = n;
break;
}
}
List<Integer> hikePlan = new ArrayList<>();
for (int t = T; t >= 1 && daysLeft >=0 && lastTrails >=0; t--) {
if (v[t][daysLeft][lastTrails] != optimalValue) {
trailsLeft = t + 1;
daysLeft--;
lastTrails--;
hikePlan.add(trailsLeft);
}
}
Collections.reverse(hikePlan);
// Printing the hike plan
int result = 0;
for(int e : hikePlan) {
result += x[e-1];
}
System.out.println(result);
}
}
我尝试了Cary Swoveland提供的解决方案，但我不清楚我哪里出错了，我得到了错误的输出。
对于输入
{3000, 1000, 4000}, 2，正确的结果是7000，但我得到了5000。同样地，对于输入{190, 200, 450, 499, 358, 160}, 3，正确的输出是849，但我得到了518。对于输入{150, 200, 400, 350, 250}, 3，正确的输出是750，但我得到了600。