https://codeforces.com/contest/903/problem/F
题目大意
给出 $4 \times n$ 的矩阵 $f$，其中有 ‘.’ 和 ‘*'。可以用 $a_i$ 点花费将 $i \times i$ 的某个子矩阵中的 ‘*’ 全部变为 ‘.'，问将整个矩阵都变为 ‘.’ 的最小花费。
$4 \le n \le 1000$。
$1 \le a_i \le 1000$ 固定给出 $i$ 为 $1, 2, 3, 4$ 的值。
简要题解
这题最开始以为是 $n \times n$ 的，感觉数据范围完全没法搞，$4 \times n$ 的就是比较显然的状态压缩 dp 了。
容易想到，如果从左向右推的话，只要维护最右边 $3$ 列的状态，因为下次转移一定无法覆盖到右数第四列。
$4$ 的转移因为直接把上次的 $3$ 列和当前列都处理了，因此需要特殊处理一下。
对于 $3$ 及其他转移，需要最左侧列是满的（都是 ‘.'），其他的情况都要舍弃，最右侧则要补充当前列的状态，以此为基础进行下一步的当前列内的转移。列内的转移，我们只需枚举所有 $1, 2, 3$ 的右边界在当前列的选与不选即可。（注意没必要枚举当前列的所有填法，只需要每种单独枚举选与不选就行了）
复杂度
$T$：$O(2^{12} \cdot 10 \cdot n)$ 这里不标准的把常数也写进来了。
$S$：$O(2^{12} + n)$
代码实现
#include <bits/stdc++.h>
using namespace std;
int io_=[](){ ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }();
using LL = long long;
using ULL = unsigned long long;
using LD = long double;
using PII = pair<int, int>;
using VI = vector<int>;
using MII = map<int, int>;
template<typename T> void cmin(T &x,const T &y) { if(y<x) x=y; }
template<typename T> void cmax(T &x,const T &y) { if(x<y) x=y; }
template<typename T> bool ckmin(T &x,const T &y) {
return y<x ? (x=y, true) : false; }
template<typename T> bool ckmax(T &x,const T &y) {
return x<y ? (x=y, true) : false; }
template<typename T> void cmin(T &x,T &y,const T &z) {// x<=y<=z
if(z<x) { y=x; x=z; } else if(z<y) y=z; }
template<typename T> void cmax(T &x,T &y,const T &z) {// x>=y>=z
if(x<z) { y=x; x=z; } else if(y<z) y=z; }
// mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
// mt19937_64 rnd_64(chrono::system_clock::now().time_since_epoch().count());
/*
---------1---------2---------3---------4---------5---------6---------7---------
1234567890123456789012345678901234567890123456789012345678901234567890123456789
*/
const int INF = 0x3f3f3f3f;
/*
8 4 0
9 5 1
10 6 2
11 7 3
*/
void solve() {
int n; cin >> n;
vector<int> a(5);
for (int i = 1; i <= 4; i++) cin >> a[i];
vector<string> s(4);
for (int i = 0; i < 4; i++) {
cin >> s[i];
}
int msk = 1 << (3 * 4);
vector<vector<int>> tran = {
{},
{(1 << 0), (1 << 1), (1 << 2), (1 << 3)},
{(1 << 0) | (1 << 1) | (1 << 4) | (1 << 5),
(1 << 1) | (1 << 2) | (1 << 5) | (1 << 6),
(1 << 2) | (1 << 3) | (1 << 6) | (1 << 7),
},
{(1 << 0) | (1 << 1) | (1 << 2) | (1 << 4) | (1 << 5) | (1 << 6) | (1 << 8) | (1 << 9) | (1 << 10),
(1 << 1) | (1 << 2) | (1 << 3) | (1 << 5) | (1 << 6) | (1 << 7) | (1 << 9) | (1 << 10) | (1 << 11),
}
};
vector<int> dp(msk, INF), tmp(msk);
dp[msk - 1] = 0;
for (int ii = 0; ii < n; ii++) {
swap(dp, tmp);
fill(dp.begin(), dp.end(), INF);
if (ii + 1 >= 4) {
int mi = INF;
for (int s = 0; s < msk; s++) {
cmin(mi, tmp[s]);
}
cmin(dp[msk - 1], mi + a[4]);
}
int all = ((1 << 4) - 1) << 8;
int line = 0;
for (int i = 0; i < 4; i++) {
line |= ((s[i][ii] == '.') << i);
}
for (int i = 0; i < (1 << 8); i++) {
cmin(dp[(i << 4) | line], tmp[i | all]);
}
for (int i = 1; i <= 3 && i <= ii + 1; i++) {
for (int ss : tran[i]) {
for (int s = 0; s < msk; s++) {
cmin(dp[s | ss], dp[s] + a[i]);
}
}
}
}
cout << dp[msk - 1] << '\n';
}
int main() {
int t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}
Next: [CF] A. Inscribed Figures - Educational Codeforces Round 64 (Rated for Div. 2)