主页 / 问题 / 1093953
Accepted
Harry
Asked:2020-03-13 01:09:43 +0800 CST2020-03-13 01:09:43 +0800 CST

DP上的奥林匹克问题

  • 772

真的很不舒服，但是...

小家伙被布置了作业——用 e-olymp 选择和解决 DP 中的任何问题。他选择了这个（下面的文字）。一小时后来找我——怎么了？为什么只有 22% 通过？

任务看起来很简单，但我显然没有看到任何东西，因为就我而言，他的代码中没有错误（好吧，除了非最优性）。戳我们 - 我们没有直接看到什么？ ...

健康）状况：

许多具有 2D 图形的旧游戏可能会遇到类似情况。什么房地产英雄跳上悬在空中的平台（或岛屿）。它必须从屏幕的一个边缘移动到另一个边缘。同时，从一个平台跳到另一个平台时，英雄拿|y 2 -y 1 | 2能量，其中 y 2和 y 1是这些平台所在的高度。此外，英雄还有一个超级招式，可以让你跳过平台，但需要花费3·|y 2 -y 1 | 2个能量单位。当然，能源应尽可能经济地使用。

假设您按从左到右的顺序知道所有平台的坐标。你能找到英雄从第一个平台到最后一个平台所需的最小能量吗？

输入数据

第一行包含平台数量 n (2 ≤ n ≤ 100000)。第二行包含 n 个不超过 4000 的自然数——平台所在的高度。

输出

打印一个数字 - 玩家克服平台必须花费的最小能量。

这是他的解决方案：

#include <iostream>

using namespace std;

long long int m[100001];
long long int h[100001];

long long int sq(long long int n) { return n*n; }

long long int min(long long int x, long long int y) { return (x < y) ? x : y; }

int main()
{
    int n;
    cin >> n;
    for(int i = 1; i <= n; ++i)
    {
        cin >> h[i];
    }
    m[1] = 0;
    m[2] = sq(h[2]-h[1]);

    for(int i = 3; i <= n; ++i)
    {
        m[i] = min(sq(h[i]-h[i-1]) + m[i-1],
                   3*sq(h[i]-h[i-2]) + m[i-2]);
    }
    cout << m[n] << endl;
}

好吧，一切都很简单——在第一个平台上，能量为 0，在第二个平台上——只是一个正方形（你只能从第一个平台上得到），然后——我们看看普通跳跃和超级跳跃的成本并取最小的......眼睛有long long int足够的范围。

c++

1 个回答

  1. Best Answer

    事实是二次函数“快速”增长，所以英雄有时会向后移动。

    例子

    11 2 10 1
11-2-1=81+3=84
11-10-1 = 3+81 =84
11-10-2-1 = 3+64+3 =70

    令 m[i] 为 1->i 的最小能量。

    让我们把 m[1] = 0。

    如果 n=2，那么我们可以通过一种方式到达第二个。

    如果 n>2，则两个 1-2 或 1-3-2。

    现在考虑计算 m[i]。

    i-platform 可以通过 (i - 1) 或 (i - 2) 访问，超级打孔。

    如果 i < n，那么您可以从 (i + 1) 到达您从 (i - 1) 跳到的 i 平台。

    m[i]=min 从

    • m[i - 1] + |yi - yi-1|^2 ：从 (i - 1) 平台正常过渡；

    • m[i - 2] + 3 * |yi - yi-2|^2 ：来自 (i - 2) 个平台的终极版；

    • m[i - 1] + 3 * |yi+1 - yi-1|^2 + |yi - yi+1|^2 : 1-3-2

    代码示例

    #define MAX 100005

...
m[1] = 0;

if (n == 2)

  m[2] = sq(h[2] - h[1]);

else

  m[2] = min(sq(h[1] - h[2]), 3 * sq(h[1] - h[3]) + sq(h[2] - h[3]));


for(int i = 3; i <= n; i++)

{

  m[i] = min(m[i - 1] + sq(h[i - 1] - h[i]), 
                m[i - 2] + 3 * sq(h[i - 2] - h[i]));

  if (i < n)
     m[i] = min(m[i], m[i - 1] + 3 * sq(h[i - 1] - h[i + 1]) + sq(h[i] - h[i + 1]));

}

 cout <<  m[n];
    • 16

相关问题