C#

Задача по программированию

Задача F. Лотерея
Рассматривается игра, в которой игрок должен попасть из одного конца квадратной карты –
в другой. Путь начинается с верхнего левого угла, заканчиваясь в противоположном углу, при чем
игрок может ходить только вниз и вправо. Карта состоит из полей, при попадании игрока в поле ему
начисляется количество очков, находящихся в этом поле. Количество очком в поле может быть
отрицательное.
Необходимо написать программу, которая по известной карте определяет, какое максимальное
количество очков может набрать игрок. Если получить положительный баланс невозможно
– необходимо вывести «NO_WIN».
Формат входных данных
В первой строке задается число N, длина стороны карты. Далее в N строках указаны
по N чисел Xi,j, разделенных пробелом, определяющих количество начисляемых очков в том или
ином поле.
2 <= N <= 50
0 <= i,j <= N-1
-1000 <= Xi,j <= 1000
Формат выходных данных
Необходимо вывести единственную строку, содержащую максимально возможный баланс
игрока, или NO_WIN, если положительный баланс невозможен.
†҉с҉в҉я҉т҉о҉й҉†҉ †҉с҉†҉
†҉с҉в҉я҉т҉о҉й҉†҉ †҉с҉†҉
238
Банальное динамическое программирование.

Последовательно проходим все ячейки матрицы (по строкам или по столбцам - не важно, главное - слева направо и сверху вниз) от a[0, 0] до a[n-1, n-1] и меняем значение каждой ячейки:
a[i, j] = a[i, j] + max(a[i - 1, j], a[i, j - 1])
тут надо правильно обработать ячейки верхней строки и левого столбца.

В результате в правой нижней ячейке получаем искомое значение.

int N;
// ввод N
int[,] a = new int[N, N];
for (int i = 0; i < N; ++i) { for (int j = 0; j < N; ++j) { /* ввод a[i, j] */ } }
for (int i = 1; i < N; ++i) {
a[i, 0] += a[i - 1, 0];
a[0, i] += a[0, i - 1];
}
for (int i = 1; i < N; ++i) { for (int j = 1; j < N; ++j) { a[i, j] += Math.Max(a[i - 1, j], a[i, j - 1]); } }
// вывод a[N - 1, N - 1]
Denis Romanoff
Denis Romanoff
64 445
Лучший ответ
Хорошая задача, поздравляю.
Павел Суходубов
Павел Суходубов
68 886
†҉с҉в҉я҉т҉о҉й҉†҉ †҉с҉†҉ Спасибо большое) Ура!!!
В принципе можно попробовать решать как задачу о максимальном потоке. Пока такая идея.
Но опять же, думаешь тут так просто за тебя решат олимпиадную задачу?
TM
Timon Maksimov
28 652
Как ты ЕГЭ сдал если ты это решить не можешь?
XX
Xxx Xxx
363
†҉с҉в҉я҉т҉о҉й҉†҉ †҉с҉†҉ Солнце, я и не сдавал ЕГЭ по информатике)
†҉с҉в҉я҉т҉о҉й҉†҉ †҉с҉†҉ Я не за дискуссиями сюда пришёл. Поноситься с тобой не собираюсь, ты, видимо, слишком умен для меня. Прости, что привлек твое внимание своей темой. Удачи)

Похожие вопросы