Решение задачи Новая Театральная площадь с Codeforces

Без пояснения   Просмотров: 1441

Возможно, вы помните Театральную площадь из задачи 1A. Сегодня ее покрытие наконец-то заменят.

Площадь все еще является прямоугольником n×m метров. Однако, рисунок на ней будет более сложным в этот раз. Пусть ai,j будет j-й ячейкой в i-м ряду покрытия плитками.

Вам задан рисунок покрытия:

если ai,j= «*», то j-я ячейка в i-м ряду должна быть черной;
если ai,j= «.», то j-я ячейка в i-м ряду должна быть белой.
Черные ячейки уже покрыты. Вам же необходимо покрыть белые ячейки. Существует две опции плиток:

1×1 плитки — каждая плитка стоит x бурлей и покрывает ровно 1 ячейку;
1×2 плитки — каждая плитка стоит y бурлей и покрывает ровно 2 соседние ячейки в одном ряду. Обратите внимание, что нельзя вращать эти плитки или резать их на плитки 1×1.
Вам необходимо покрыть все белые ячейки, никакие две плитки не должны накладываться друг на друга и никакие черные ячейки не должны быть накрыты плитками.

Чему равна наименьшая суммарная цена плиток, которые могут покрыть все белые клетки?

Код 

#include <bits/stdc++.h>
using namespace std;
						
#define fast_cin() ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define endl '\n'
#define int long long

void testcase() {
	int n, m; cin >> n >> m;
	int x, y; cin >> x >> y;
	y = min(y, 2 * x);
	int ans = 0;
	string s[n];
	for (int i = 0; i < n; ++i) {
		cin >> s[i];
		for (int j = 0; j < m; ++j) {
			if (s[i][j] == '.') {
				if (j + 1 < m && s[i][j + 1] == '.') {
					ans += y;
					++j;
				} else {
					ans += x;
				}
			}
		}
	}
	cout << ans << endl;
}
				
int32_t main() {
	fast_cin();  
	int T; cin >> T;
	while (T--) {
		testcase();
	}
	return 0;
}

         

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



Комментарии

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



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

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

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