@codeforces - 1209E2@ Rotate Columns (hard version)

左手的ㄟ右手 2023-06-01 12:57 59阅读 0赞

*  @description@
 *  @solution@
 *  @accepted code@
 *  @details@

--------------------

## @description@ ##

给定一个 n\*m 的矩阵 A。  
定义一次操作为将矩阵的某一列竖着循环移位，你可以对任意列做任意次操作。  
定义 ri 为第 i 行的最大值，最大化 r1 + r2 + ... + rn。

**Input**  
第一行一个整数 t (1≤t≤40)，表示数据组数。  
每组数据第一行包含两个整数 n m (1≤n≤12,1≤m≤2000) 表示 A 矩阵的行数与列数。  
接下来 n 行每行 m 个整数，表示 A 中的元素。(1≤ai,j≤10^5)。

**Output**  
输出 t 个整数：每组数据的答案。

**Example**  
**Input**  
3  
2 3  
2 5 7  
4 2 4  
3 6  
4 1 5 2 10 4  
8 6 6 4 9 10  
5 4 9 5 8 7  
3 3  
9 9 9  
1 1 1  
1 1 1  
**Output**  
12  
29  
27

**Note**  
第一组数据，只需要将第三行进行操作，得到 r1 = 5, r2 = 7。  
第二组数据，不需要进行任何操作，得到 r1 = r2 = 10, r3 = 9。

## @solution@ ##

n <= 12 暗示你状压。

每一行的最大值之和最大，其实可以理解为每一行任意选择一个数使它们的和最大。  
于是我们可以不考虑元素是不是该行最大值。

定义 dp\[i\]\[s\] 表示前 i 列已经被选择的行构成集合 s，显然可以滚动数组。  
通过枚举第 i + 1 列循环移位的次数，以及第 i + 1 列选择哪些元素计入答案（枚举子集）就可以转移。  
但是时间复杂度 O(t\*3^n\*n\*m) 过不了。

一个没什么用的优化：在确定循环移位次数后，我们不枚举子集，而是逐个加入元素。这样就可以将 O(3^n) 降为 O(2^n\*n)。  
但是时间复杂度 O(t\*2^n\*n^2\*m) 还是过不了，不过因为代码是这么写的所以提一下。

问题最关键的点在于，n 和 m 不是等阶的。  
注意到当 m >= n 时，我们总是存在一个方案：选 n 列，使得这 n 列的最大值之和最大。  
其实就是给 m 列按照每一列的最大值从大到小排序，取前 n 列。

可以证明只需要这 n 列就可以组合出最终答案。  
假如你选择了这 n 列以外的列，共选出 k 行。那么这 n 列中就有 k 列没选到，可以将这 k 列的最大值去替换 n 列以外的 k 行。

于是时间复杂度降为 O(t\*2^n\*n^3 + T(sort))。

## @accepted code@ ##

#include<cstdio> #include<algorithm> using namespace std; const int MAXN = 12; const int MAXM = 2000; int a[MAXN + 5][MAXM + 5], n, m; int f[1<<MAXN], g[1<<MAXN], h[1<<MAXN], lg[1<<MAXN]; int lowbit(int x) {return x & -x;} struct node{ int key, id; friend bool operator < (node a, node b) { return a.key > b.key; } }arr[MAXM + 5]; bool tag[MAXM + 5]; void solve() { scanf("%d%d", &n, &m); for(int j=1;j<=m;j++) tag[j] = false, arr[j].key = 0, arr[j].id = j; for(int i=0;i<n;i++) for(int j=1;j<=m;j++) scanf("%d", &a[i][j]), arr[j].key = max(arr[j].key, a[i][j]); sort(arr + 1, arr + m + 1); for(int i=1;i<=m&&i<=n;i++) tag[arr[i].id] = true; int tot = (1<<n); for(int j=0;j<tot;j++) f[j] = 0; for(int j=0;j<n;j++) lg[1<<j] = j; for(int i=1;i<=m;i++) { if( !tag[i] ) continue; for(int j=0;j<tot;j++) h[j] = 0; for(int j=1;j<=n;j++) { for(int k=0;k<tot;k++) g[k] = f[k]; for(int k=0;k<tot;k++) { int p = (tot - 1)^k; while( p ) { int x = lowbit(p), y = lg[x]; g[k|x] = max(g[k|x], g[k] + a[y][i]); p -= x; } } int tmp = a[0][i]; for(int k=0;k<n-1;k++) a[k][i] = a[k + 1][i]; a[n - 1][i] = tmp; for(int j=0;j<tot;j++) h[j] = max(h[j], g[j]), g[j] = 0; } for(int j=0;j<tot;j++) f[j] = h[j]; } printf("%d\n", f[tot - 1]); } int main() { int t; scanf("%d", &t); while( t-- ) solve(); }

## @details@ ##

感觉看完题解都不能理解昨天晚上在干什么。。。

这种通过分析最终答案的下界，以此压缩状态的题虽然比较少见，但是见过的。。。  
果然还是我太菜。。。

转载于:https://www.cnblogs.com/Tiw-Air-OAO/p/11521194.html