Educational Codeforces Round 88 (Rated for Div. 2) B. New Theatre Square（贪心）

题目链接：https://codeforces.com/contest/1359/problem/B

题意

有一块 $n imes m$ 的地板和两种瓷砖：

• $1 imes 1$，每块花费为 $x$
• $1 imes 2$，每块花费为 $y$

地板为 '.' 表示未铺瓷砖，瓷砖不可旋转， 问铺满瓷砖的最小花费。

题解

因为 $1 imes 2$ 的瓷砖不能旋转，所以每次逐行考虑即可，注意 $y$ 取 $min(2x, y)$ 。

代码

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int n, m, x, y; cin >> n >> m >> x >> y;
    y = min(2 * x, y);
    int ans = 0;
    for (int i = 0; i < n; i++) {
        string s; cin >> s;
        for (int j = 0; j < m; j++) {
            if (s[j] == '.') {
                if (j + 1 < m and s[j + 1] == '.')
                    ans += y, ++j;
                else 
                    ans += x;
            }
        }
    }
    cout << ans << "
";
}

int main() {
    int t; cin >> t;
    while (t--) solve();
}