F - Clear The Matrix
分析
题目问将所有星变成点的花费，限制了行数（只有4行），就可以往状压DP上去靠了。
\(dp[i][j]\) 表示到第 \(i\) 列时状态为 \(j\) 的花费，只需要记录 16 位二进制，因为我们最多只能影响到 4 * 4 的星，那么每次都是从一个 4 * 4 的矩阵转移到一个 4 * 4 的矩阵，注意，转移时必须保证最左边列全部为 1 （即都是星号），那么最后答案就是 \(dp[n][(1 << 16) - 1]\)。
比如我们选定点 (i, j)，将 3 * 3 的星变成点，那么变的就是左上角 (i, j - 2) 右下角 (i + 2, j) 的这个矩阵。
为了状态转移，我们会同时对一列的星进行变换，可能有多种方案，这个可以预处理再加些优化，最后合法的是很少的。
code
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
string mp[4];
int dp[2][1 << 16];
int n, cnt, a[5], b[133], c[133];
int calc(int xl, int xr, int yl, int yr) {
int res = 0;
for (int i = xl; i <= xr; i++) {
for (int j = yl; j <= yr; j++) {
res += 1 << ((i * 4) + j);
}
}
return res;
}
void dfs(int x, int mx, int st, int cost) {
if (x == 4) {
b[cnt] = st;
c[cnt++] = cost;
return;
}
for (int i = 4; i >= 1; i--) {
if (x + i > 4) continue;
if (!x) {
dfs(x + 1, i, st | calc(4 - i, 3, x, i - 1), cost + a[i]);
} else {
if (x + i > mx) {
dfs(x + 1, x + i, st | calc(4 - i, 3, x, x + i - 1), cost + a[i]);
} else {
break;
}
}
}
dfs(x + 1, x, st, cost);
}
int main() {
cin >> n >> a[1] >> a[2] >> a[3] >> a[4];
for (int i = 0; i < 4; i++) {
cin >> mp[i];
}
dfs(0, 0, 0, 0);
memset(dp[0], 0x3f, sizeof dp[0]);
dp[0][(1 << 16) - 1] = 0;
int cur = 0;
for (int i = 0; i < n; i++) {
int cst = 0;
for (int j = 0; j < 4; j++) {
if (mp[j][i] == '.') {
cst += 1 << (12 + j);
}
}
cur = !cur;
memset(dp[cur], 0x3f, sizeof dp[cur]);
for (int j = 0; j < (1 << 12); j++) {
dp[cur][j | cst] = dp[!cur][(j << 4) + 15];
if (dp[!cur][(j << 4) + 15] == 0x3f3f3f3f) continue;
for (int k = 0; k < cnt; k++) {
dp[cur][j | cst | b[k]] = min(dp[!cur][(j << 4) + 15] + c[k], dp[cur][j | cst | b[k]]);
}
}
}
cout << dp[cur][(1 << 16) - 1] << endl;
return 0;
}
G. Yet Another Maxflow Problem
分析
一道“网络流”的题目。
本题主要注意最小割等于最大流，我们去构造这个解，即怎样才算最小割。注意到本题边的限制颇多，\(A_i\)-\(A_{i+1}\) 连有向边，\(B_i\)-\(B_{i+1}\) 连有向边，且从 A 到 B 连有向边，考虑 A 这部分，如果删掉边 \(A_i\)-\(A_{i+1}\) ，那么 \(A_{i+1}\) 下面所有边都无意义了，对于 B 这部分，删掉 \(B_i\)-\(B_{i+1}\)，则 \(B_i\) 上面所有边都无意义了，有这样的性质后，我们枚举左边的边，用线段树维护删掉右边的边的代价的最小值（右边也有可能不删），用 multiset 维护全局最优解。
code
#include <bits/stdc++.h>
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
using namespace std;
const int N = 2e5 + 10;
int a[N], b[N];
vector<pair<int, int> > G[N];
long long s[N << 4], lazy[N << 4];
void pushDown(int rt) {
lazy[rt << 1] += lazy[rt];
lazy[rt << 1 | 1] += lazy[rt];
s[rt << 1] += lazy[rt];
s[rt << 1 | 1] += lazy[rt];
lazy[rt] = 0;
}
void pushUp(int rt) { s[rt] = min(s[rt << 1], s[rt << 1 | 1]); }
void build(int l, int r, int rt) {
if (l == r)
s[rt] = b[l - 1];
else {
int m = l + r >> 1;
build(lson);
build(rson);
pushUp(rt);
}
}
void update(int L, int R, int c, int l, int r, int rt) {
if (l >= L && r <= R) {
lazy[rt] += c;
s[rt] += c;
} else {
pushDown(rt);
int m = l + r >> 1;
if (m >= L) update(L, R, c, lson);
if (m < R) update(L, R, c, rson);
pushUp(rt);
}
}
long long query(int L, int R, int l, int r, int rt) {
if (l >= L && r <= R)
return s[rt];
else {
pushDown(rt);
int m = l + r >> 1;
long long res = (1LL << 62);
if (m >= L) res = query(L, R, lson);
if (m < R) res = min(res, query(L, R, rson));
pushUp(rt);
return res;
}
}
multiset<long long> mset;
long long cb[N];
int main() {
int n, m, q;
cin >> n >> m >> q;
for (int i = 1; i < n; i++) {
scanf("%d%d", &a[i], &b[i]);
}
for (int i = 0; i < m; i++) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
G[u].push_back(pair<int, int>(v, w));
}
build(1, n, 1);
for (int i = 1; i <= n; i++) {
for (int j = 0; j < G[i].size(); j++) {
update(1, G[i][j].first, G[i][j].second, 1, n, 1);
}
cb[i] = s[1];
mset.insert(cb[i] + a[i]);
}
printf("%I64d\n", *mset.begin());
while (q--) {
int v, w;
scanf("%d%d", &v, &w);
mset.erase(mset.lower_bound(a[v] + cb[v]));
a[v] = w;
mset.insert(w + cb[v]);
printf("%I64d\n", *mset.begin());
}
return 0;
}