Динамическое программирование, алгоритм

#cpp #алгоритм

Задача такая:


  Дано положительное число n, целые числа в порядке возрастания
  p1 < p2 < ... < pk, и c1,
  c2, ..., ck (0 < k < 10^5; 0 <= n, pi
  < 10^9, 0 < ci < 10^9).  pi - координаты точек
  на оси, ci - их веса. Нужно выбрать точки так, чтобы сумма
  их весов была максимальной, но расстояние между любой парой точек было
  не меньше n (n - расстояние на оси).


Я делал так - на i-м шаге для каждой точки запоминал число, равное максимальной допустимой
сумме совокупности i точек с учётом их весов, расположенных по возрастанию, и оканчивающейся
данной точкой.

В общем случае не работает (неверный ответ), но я не смог найти примеров с ошибкой.
Помогите, пожалуйста, разобраться.



Тестовый пример (на обоих программа работает верно):


Ввод

4 10
5 10 15 20
100 50 100 300


Вывод

400

Ввод 

5 15
2 14 25 31 37
8 19 20 11 25


Вывод

44





#include 
#include 
#include 

std::vector f(const std::vector &first, const std::vector &v1, const
std::vector &v2, int n1, int n2) {
    int a = -1000000000;
    std::vector ans(n1);
    for (int i = 0; i != n1; ++i) {
        if (v1[i] <= n2) {
            ans[i] = a;
        } else {
            std::vector A(n1);
            int j = 0;
            while (abs(v1[i] - v1[j]) > n2) {
                A[j] = first[j];
                ++j;
            }
            int m = *std::max_element(A.begin(), A.end());
            if (m == 0) {
                ans[i] = a;
            } else {
                ans[i] = m + v2[i];
            }
        }
    }
    return ans;
}

int main() {
    int n1, n2;
    std::cin >> n1 >> n2;
    std::vector v1(n1);
    for (size_t i = 0; i != n1; ++i) {
        std::cin >> v1[i];
    }
    std::vector v2(n1);
    for (size_t i = 0; i != n1; ++i) {
        std::cin >> v2[i];
    }
    std::vector ans;
    std::vector c = f(v2, v1, v2, n1, n2);
    ans.push_back(*std::max_element(c.begin(), c.end()));
    for (int i = 0; i != n1; ++i) {
        std::vector x = f(c, v1, v2, n1, n2);
        ans.push_back(*std::max_element(x.begin(), x.end()))
        c = x;
    }
    std::cout << *std::max_element(ans.begin(), ans.end());
    return 0;
}

    

Ответы

Ответ 1

Учитывая, что все веса положительные, все точки удовлетворяющие вашему условию |P[i]
- P[j]| < n, i # j и будут решением. Это очевидно.