Решение задачи Уменьшение высот с Codeforces

С пояснением   Просмотров: 967

Вы играете в одну популярную sandbox-игру с трехмерным миром. Карта мира может быть представлена в виде матрицы размера n×m, где высота клетки (i,j) равна ai,j.

Сейчас вы находитесь в клетке (1,1) и хотите попасть в клетку (n,m). Вы можете перемещаться только вниз (из клетки (i,j) в клетку (i+1,j)) или вправо (из клетки (i,j) в клетку (i,j+1)). Также есть дополнительное ограничение: если высота текущей клетки равна x, то вы можете переместиться только в клетку с высотой x+1.

Перед первым перемещением вы можете выполнить несколько операций. В течение одной операции вы можете уменьшить высоту любой клетки на единицу. То есть вы выбираете какую-то клетку (i,j) и присваиваете ai,j:=ai,j−1. Заметьте, что вы можете делать высоты меньшими или равными нулю. Также заметьте, что вы можете уменьшать высоту клетки (1,1).

Ваша задача — найти минимальное количество операций, которое необходимо выполнить, чтобы получить хотя бы один подходящий путь из клетки (1,1) в клетку (n,m). Гарантируется, что ответ существует.

Вам необходимо ответить на t независимых наборов тестовых данных.

Код 

#include <bits/stdc++.h>

using namespace std;

#define forn(i, n) for (int i = 0; i < int(n); ++i)

const long long INF64 = 1e18;

int main() {
	int t;
	cin >> t;
	while (t--) {
		int n, m;
		cin >> n >> m;
		vector<vector<long long>> a(n, vector<long long>(m));
		forn(i, n) forn(j, m) {
			cin >> a[i][j];
		}
		long long a00 = a[0][0];
		long long ans = INF64;
		forn(x, n) forn(y, m) {
			long long need = a[x][y] - x - y;
			if (need > a00) continue;
			a[0][0] = need;
			vector<vector<long long>> dp(n, vector<long long>(m, INF64));
			dp[0][0] = a00 - need;
			forn(i, n) forn(j, m) {
				long long need = a[0][0] + i + j;
				if (need > a[i][j]) continue;
				if (i > 0) dp[i][j] = min(dp[i][j], dp[i - 1][j] + a[i][j] - need);
				if (j > 0) dp[i][j] = min(dp[i][j], dp[i][j - 1] + a[i][j] - need);
			}
			ans = min(ans, dp[n - 1][m - 1]);
		}
		cout << ans << endl;
	}
	
	return 0;
}

         

Администратор Photo Автор: Администратор


Пояснение к задаче

Для начала, рассмотрим поле в 0-индексации. Допустим, что клетка (0,0) имеет какую-то фиксированную высоту. Пусть она равна b0,0. Тогда мы можем определить высоту, которую должна иметь клетка (i,j), как bi,j=b0,0+i+j. Фактически нам не важно, кааой путь мы выбираем, на самом деле нам нужно знать только количество ходов, необходимое для того, чтобы достичь клетку, а также высоту клетки (0,0).

Тогда (когда высота клетки (0,0) фиксирована), мы можем решить задачу следующим динамическим программированием: dpi,j равно минимальному количеству операций, которое нам необходимо, чтобы достичь клетки (i,j) из клетки (0,0). Изначально все значения dpi,j=+∞, кроме dp0,0=0. Тогда dpi,j может быть посчитано как min(dpi−1,j,dpi,j−1)+(ai,j−bi,j). Но еще один важный момент: если ai,j
Но если мы будем перебирать все возможные высоты, наше решение абсолютно точно получит вердикт time limit exceeded. Теперь мы можем заметить один важный факт: в оптимальном ответе высота какой-то клетки останется неизменной. Пусть эта клетка равна (i,j). Тогда мы можем восстановить высоту клетки (0,0) как ai,j−i−j и запустить наше кваратичное динамическое программирование, чтобы найти ответ для этой высоты.

Асимптотика решения: O(n4).


Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться



info@mycod.net   Карта сайта   Правообладателям
Заявка на расчет
×

или напишите нам прямо сейчас:

Написать в MAX
Написать в Telegram
Написать в WhatsApp