почему код плохо указывает позиции?

Question

почему код плохо указывает позиции?

Рейтинг: -1Ответов: 2Опубликовано: 21.03.2023

В общем вот задачка: Тренер хочет собрать команду из баскетболистов. Игроки стоят в двух рядах, каждый ряд содержит n игроков. Каждый игрок указывает, сколько максимально он может набрать очков в одной игре. Тренер хотел бы сформировать команду с максимальным количеством очков, но есть ограничение: если выбран один игрок, то нельзя выбрать другого игрока, стоящего рядом с ним (слева, справа, сверху или снизу). Помогите тренеру найти команду с максимальным количеством очков.

Ввод: число n и две последовательности чисел a[i], b[i] (1 <= n <= 2 * 10^4, 1 <= a[i] <= 10^9). Вывод: В первой строке - общее количество очков лучшей возможной команды. Во второй строке - количество выбранных игроков баскетбольной команды. В следующей строке напечатайте позиции выбранных игроков баскетбольной команды тренером (номера столбцов и строк). Печатайте начиная с самого левого игрока.

#include <iostream>
#include <algorithm>
using namespace std;
 
int main() {
int n;
cin >> n;

int a[n+1], b[n+1];
for (int i = 1; i <= n; i++) {
    cin >> a[i];
}
for (int i = 1; i <= n; i++) {
    cin >> b[i];
}

int f[n+1][2] ;
f[0][0] = f[0][1] = 0;

for (int i = 1; i <= n; i++) {
    f[i][0] = max(f[i-1][1], (i > 1 ? f[i-2][1] : 0)) + a[i];
    f[i][1] = max(f[i-1][0], (i > 1 ? f[i-2][0] : 0)) + b[i];
}

int selected[n+1];
int max_points = max(f[n][0], f[n][1]);
int i = n, j = max_points == f[n][0] ? 0 : 1;
while (i >= 1) {
    if (j == 0) {
        if (f[i][0] == f[i-1][1] + a[i]) {
            selected[i] = 1;
            i--;
            j = 1;
        } else {
            i -= 2;
        }
    } else {
        if (f[i][1] == f[i-1][0] + b[i]) {
            selected[i] = 2;
            i--;
            j = 0;
        } else {
            i -= 2;
        }
    }
}

cout << max_points << endl;

int num_selected = 0;
for (int i = 1; i <= n; i++) {
    if (selected[i] != 0) {
        num_selected++;
    }
}
cout << num_selected << endl;

for (int i = 1; i <= n; i++) {
    if (selected[i] == 1) {
        cout << i << " " << 1 << endl;
    } else if (selected[i] == 2) {
        cout << i << " " << 2 << endl;
    }
}

return 0;
}

Но этот код неправильно определяет позиции выбранных баскетболистов, например, если ввести: 3 1 2 9 10 1 1 Ответ должен быть: 19 2 1 2 3 1 Но в этом коде вместо 1 2 и 3 1 выдаёт 1 1 и 2 1.

Но вот если ввести:

5
9 3 5 7 3
5 8 1 4 5

То ответ правильный:

Так вот вопрос почему, почему он плохо указывает позиции выбранных баскетболистов? Где я делаю ошибку?

c#

Источник: Stack Overflow на русском

Answer 1

▲ 0

В главном цикле не используйте max, а сами сравнивайте выражения, и выбирайте, и при этом записывайте, какой вариант использован, в параллельный массив. После этого достаточно будет обойти этот параллельный массив.

Answer 2

▲ 0

Во-первых, на первом примере этот код выдает

19
1
1 1

Это потому, что после выбора первого элемента как максимума, вы добавляете в selected[i] индикатор только если решение пришло по диагонали.

int max_points = max(f[n][0], f[n][1]);
int i = n, j = max_points == f[n][0] ? 0 : 1;
// selected[i] =  (max_points == f[n][0] ? 1 : 2);   // нужно добавить
while (i >= 1) {
    if (j == 0) {
        if (f[i][0] == f[i-1][1] + a[i]) { // если решение по диагонали
            selected[i] = 1;  // добавляем элемент
            i--;
            j = 1;
        } else {   // а если решение не по диагонали - не добавляем
            i -= 2;
        }
    }

почему код плохо указывает позиции?

Ответы