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

Задача такая:
Дано положительное число 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; }

Ответ

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