主页 / 问题 / 1586518
Accepted
Роман
Asked:2024-07-08 18:40:49 +0000 UTC2024-07-08 18:40:49 +0000 UTC

Frog 的动态规划问题

  • 772

我有一个无法解决的问题。看起来这个任务看起来像是一个 DP 任务。我就是这样解决的。

int main() {

long long n; cin >> n;
vector<long long> kuv;
kuv.push_back(0);
for(long long i = 1; i < n + 1; i++){
    kuv.push_back(0);
    cin >> kuv[i];
    //  cerr << kuv[i] << " ";
}
//  cerr << "\n" << n << " " << n +2 << "  ----------\n";
long long x, y; cin >> x >> y;
vector<long long> te (n + 2, -1);
//  cerr << "------------" << size(te) << " --------\n";
te[0] = 0;

for(long long i = 0; i < n + 2; i++){
    for(long long j = i+x; ((j < (i + y)) &&  (j < n+1)); j++){
        // cerr << i << " " << j << "\n";
        // cerr << te[j] << " ";
        // cerr << te[i] << " ";
        // cerr << kuv[j] << "\n";
        te[j] = max(te[j], te[i]+ kuv[j]);
    }
}
/*
for(int i = 0; i < n+2; i++){
    cout << te[i] << " ";
}
 */
cout << te[n];




return 0;

}

但它给出了 TL。我无法想象还有哪些地方可以优化。这是任务本身：

从前，在一片茂密的森林里，住着一种特殊的青蛙，名叫青蛙。他具有令人难以置信的能力，可以向前跳跃整个数量的单元格，但有一个限制：她的跳跃长度只能是从 X X 到 Y Y 单元格（包括两个边界）。青蛙梦想征服森林中最长、最神秘的小路——从起点到终点。

有一天，青蛙发现自己面前有一长段N个N个细胞，每个细胞里都有一定的数字。这些数字代表了一张神秘的地图，显示了青蛙在每个转弯处可能会得到什么奖励。青蛙意识到，为了实现他的梦想，他需要选择一条能让他收集最多宝藏的道路。

青蛙就这样开始了他的奇妙旅程。最初，他站在0号牢房里。对他来说，重要的不仅是到达终点，而且一路上收集到最大的金额。

你不能跳回来。跳跃长度是最终坐标和初始坐标之间的差值。如果青蛙在单元格 1 中，X X = 2，Y Y = 5，那么在 1 次跳跃中，您最终可以到达单元格 3、4、5、6。

输入格式 在第一行中输入数字 N N ( 1 ≤ N ≤ 4 * 1 0 5 1≤N≤4*10 5 ) − − 路径上的单元格数量。在第二行中，以空格分隔，输入数字 a i a i ​ ( 1 ≤ a i ≤ 1 0 9 1≤a i ≤10 9 ) − − 青蛙通过此单元格将收到的宝藏数量。在第三行中，输入两个数字 X X 和 Y Y，以空格分隔 ( 10 ≤ X ≤ Y ≤ 1 0 5 10≤X≤Y≤10 5 ) − − 跳转的最小和最大长度。

输出格式 在一行中，打印从路径的第一个单元格走到最后一个单元格可以获得的最大宝藏数量。如果无法跳转到终点，则输出-1。

示例 1 输入 输出 10 6 2 2 2 8 3 9 1 2 1 10 100000 1 示例 2 输入 输出 11 5 6 4 7 6 2 9 7 2 2 7 12 13

c++

1 个回答

  1. Best Answer

    你的算法结果是二次 O(N*(YX))。 10^5 数量级的约束意味着需要更好的复杂性，最好是 N 中的线性。

    为此，您可以使用数据结构“dec”( std::deque)。该向量te将存储到达的每个位置的最佳结果。

    该牌组存储向量索引te（可能是索引+值对），它们可以是某个结果位置的最佳前驱的候选者。对于单元格中的结果te[i]，要跳转的最佳前导是大小窗口中最大值的索引y-x+1，与当前位置间隔x

    在每一步中，您都会检查牌组头部的索引是否已过时 - 如果与当前索引的差值超过 Y，则删除该头部。

    然后将索引X从当前的索引中取出，并将该索引对应的值与牌组尾部指向的值进行比较。只要te[i-X]大于等于从尾部开始的值，就去掉尾部——这些元素不再有机会，因为有更年轻和更昂贵的。

    添加te[i-X]到尾巴。

    现在头部包含当前位置的最佳前驱的索引，我们将总和写入结果的当前位置kuv[i] + te[deque.head]

    每个元素添加和删除一次，算法是线性的。

    #include <iostream>
#include <deque>
#include <vector>
using namespace std;

int main() {

    vector<int> kuv = { 0, 12, 2, 13, 9, 4, 7, 15, 5, 12, 4, 7, 19, 2, 15, 7, 0 };
    int n = kuv.size();
    int x = 2;
    int y = 5;
    int imax;
    vector<int> te(n);
    deque <int> deq;
    for (int i = x; i < n; i++) {
        if (!deq.empty() && i - deq.front() >= y)
            deq.pop_front();
         while (!deq.empty() && te[i - x] >= te[deq.back()])
             deq.pop_back();
         deq.push_back(i - x);
         te[i] = te[deq.front()] + kuv[i];
    }
    cout << te[n-1];
    return 0;
 }

    类似Python 程序的输出（位置、牌组中的索引、结果）

    [0, 12, 2, 13, 9, 4, 7, 15, 5, 12, 4, 7, 19, 2, 15, 7, 0]
2 [0] 2
3 [1] 13
4 [2] 11
5 [3] 17
6 [3, 4] 20
7 [5] 32
8 [6] 25
9 [7] 44
10 [7, 8] 36
11 [9] 51
12 [9, 10] 63
13 [11] 53
14 [12] 78
15 [12, 13] 70
16 [14] 78
    • 2

相关问题