2019 年 CCPC 秦皇岛 G Game on Chessboard 题面 给定一个 12 × 12 的正方形棋盘,放了黑白两种棋子,每个格子有权值 w ( i , j ) 。有两种操作,删除一个棋子 ( i , j ) ,花费为 w ( i , j ) ,删除一对黑白棋子 ( i 1 , j 1 ) 和 ( i 2 , j 2 ) ,并且满足这两个棋子的左下角范围内不能有其它棋子,花费为 | w ( i 1 , j 1 ) − w ( i 2 , j 2 ) | 。求删除所有棋子的最小花费。
分析 注意到,每次能够删除的棋子在一条从坐上到右下的轮廓线上,对轮廓线进行状压,0 表示向下,1 表示向右。
轮廓线有 2n \choose n 条,状压枚举时,找到拐角点进行转移。
时间复杂度 O(n^2 {2n \choose n}) 。
2020 年 ICPC 上海 F Fountains 题面 给定一个长度为 9 的序列 a_1, a_2, \dots, a_n ,求选出 k=1,2,\dots,\frac{n(n+1)}{2} 个不同的子区间时,最大化 \sum_{L \le R} \max_{i=1}^k [L \le l_i \le r_i \le R] w(l_i, r_i) ,其中 w(l,r)=\sum_{i=l}^r a_i 。
分析 首先,我们将线段 [l,r] 看成平面上的一个点 (l,r) ,显然这个点左上角的点对应线段都包含线段 [l,r] 。
对所有子区间线段按权值由大到小排序,考虑 dp(i,j,S) 表示考虑到了前 i 条线段,选出了 j 个,状态 S 内的所有区间都已经确定了包含的线段,显然 S 是一个从左下角到右上角的轮廓线。当我们枚举下一个放进来的线段时,就和原有状态求一个并,因为排序的缘故,只需要更新没有更新过的点的答案,同时维护出新的轮廓线。
时间复杂度 O((\frac{n(n+1)}{2})^2 {2n \choose n}) 。
代码 Game on Chessboard 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 #include <iostream> #include <cstdio> #include <cassert> #include <cstring> #include <cmath> #include <functional> #include <algorithm> #include <utility> #include <vector> #include <string> #include <queue> #define ms(a,b) memset(a,b,sizeof(a)) using namespace std;using ll = long long ;using PII = pair<int ,int >;const int mod = 998244353 ;const int inf = 1 << 30 ;const int maxn = 20 + 5 ;int getBit (int x, int b) { return x >> b & 1 ; } int n, a[maxn][maxn], col[maxn][maxn];char s[maxn];int dis[(1 << 24 ) + 5 ];int main () { scanf ("%d" , &n); for (int i = 0 ; i < n; i++) { scanf ("%s" , s); for (int j = 0 ; j < n; j++) { if (s[j] == 'W' ) { col[i][j] = 1 ; } else if (s[j] == 'B' ) { col[i][j] = 2 ; } } } for (int i = 0 ; i < n; i++) { for (int j = 0 ; j < n; j++) { scanf ("%d" , &a[i][j]); } } ms (dis, -1 ); int st = ((1 << n) - 1 ) << n, ed = (1 << n) - 1 ; dis[st] = 0 ; vector<int > corner; vector<int > ca, cc; for (int u = st; u >= ed; u--) { if (__builtin_popcount(u) != n) continue ; if (dis[u] == -1 ) continue ; int x = 0 , y = 0 ; corner.clear (); ca.clear (); cc.clear (); for (int i = 0 ; i + 1 < n + n; i++) { if (getBit (u, i) == 0 && getBit (u, i + 1 ) == 1 ) { if (col[x][y]) { corner.emplace_back (i); ca.push_back (a[x][y]); cc.push_back (col[x][y]); } int nxt = u ^ (1 << i) ^ (1 << (i + 1 )); int val = dis[u]; if (col[x][y]) { val += a[x][y]; } if (dis[nxt] == -1 || dis[nxt] > val) { dis[nxt] = val; } } if (getBit (u, i) == 0 ) { x++; } else { y++; } } for (int i = 0 ; i < corner.size (); i++) { for (int j = 0 ; j < i; j++) { if (cc[i] != cc[j]) { int nxt = u; nxt ^= (1 << corner[i]) ^ (1 << (corner[i] + 1 )); nxt ^= (1 << corner[j]) ^ (1 << (corner[j] + 1 )); int val = dis[u] + abs (ca[i] - ca[j]); if (dis[nxt] == -1 || dis[nxt] > val) { dis[nxt] = val; } } } } } printf ("%d\n" , dis[ed]); return 0 ; }
Fountains 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 #include <iostream> #include <cstdio> #include <cassert> #include <cstring> #include <cmath> #include <functional> #include <algorithm> #include <utility> #include <vector> #include <string> #include <unordered_map> #include <bitset> #define ms(a,b) memset(a,b,sizeof(a)) using namespace std;using ll = long long ;using PII = pair<int ,int >;const int mod = 998244353 ;const int inf = 1 << 30 ;const int maxn = 100 + 5 ;int n, a[maxn];ll pre[maxn]; unordered_map<bitset<maxn>,ll> f[maxn], g[maxn]; int main () { scanf ("%d" , &n); for (int i = 1 ; i <= n; i++) { scanf ("%d" , a + i); pre[i] = pre[i - 1 ] + a[i]; } ll sum = 0 ; vector<PII> line; for (int i = 1 ; i <= n; i++) { for (int j = i; j <= n; j++) { sum += pre[j] - pre[i - 1 ]; line.emplace_back (i, j); } } sort (line.begin (), line.end (), [&](const PII& lhs, const PII& rhs) { ll a = pre[lhs.second] - pre[lhs.first - 1 ]; ll b = pre[rhs.second] - pre[rhs.first - 1 ]; return a > b; }); f[0 ][0 ] = 0 ; for (int i = 0 ; i < line.size (); i++, swap (f, g)) { for (int j = 0 ; j <= i + 1 ; j++) { g[j].clear (); } ll cur = pre[line[i].second] - pre[line[i].first - 1 ]; for (int j = 0 ; j <= i; j++) { for (auto & x: f[j]) { auto state = x.first; ll val = x.second; g[j][state] = max (g[j][state], val); for (int l = 1 ; l <= line[i].first; l++) { for (int r = line[i].second; r <= n; r++) { if (!state[n * (l - 1 ) + (r - 1 )]) { val += cur; state[n * (l - 1 ) + (r - 1 )] = 1 ; } } } g[j + 1 ][state] = max (g[j + 1 ][state], val); } } } for (int i = 1 ; i <= n * (n + 1 ) / 2 ; i++) { ll val = 0 ; for (auto & x: f[i]) { val = max (val, x.second); } printf ("%lld\n" , sum - val); } return 0 ; }