Codeforces Round 584 - Dasha Code Championship - Elimination Round

發表於 更新於 分類於 ， Disqus： 文章字數： 867 所需閱讀時間 ≈ 3 分鐘
E (状压DP + 常数优化)

原题链接

2400 评分

大意

n*m的数字矩阵

你可以对任意个列，进行列的循环移动任意次 (cyclical shifts)

问 能得到的((每行最大值之和)的最大值)是多少

数据范围

1<=n<=12, 1<=m<=2000

0<=矩阵中的数字<=100'000

3s

256MB

题解

其实还有题目E1,也就是n最大只有4

显然 我们按照每列最大元素 进行排序，只需要取最大的min(n,m)列，再旋转即可

那么问题来了,问题简化为 最大 12*12的矩阵

如果有一个12*12要怎么做呢

无脑枚举可以做E1,因为只有 4^4,而E2有 12^12

方法是 dp, 状态dp[i][state]

其中 state是 选取的行的状态二进制编码 O(2^n),

整个dp表示 前i列,行的选取状态为state时的最大值

那么答案为 dp[m-1][(1<<n)-1]

状态转移

dp[i][stateX] = max(dp[i-1][stateY]+ sum{矩阵第i列,stateX-stateY选中的行的元素的值 } )

意义就是 前i列 选取行的状态是stateX的话

那么 它的最大期望 是 选取的一部分(stateX-stateY)来自第i列，其余(stateY)来自前i-1列

那么状态转移，对当前列 循环n次移动，每次计算 所有状态, 的所有状态来源

一次状态转移时间复杂度为 O(n(shift移动当前列) * (1<<n)(所有状态) * n(每个状态的来源) )

总的一次状态转移为 O( min(n,m) * n * (1<<n) * n )

12^3*2^12 = 7077888 有注意常数的必要

代码

Accepted Code

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
97
98
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
#define MOD 1000000007
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
const double pi = acos(-1.0);
 
const int MAXN = 12;
const int MAXM = 2000;
int a[MAXN + 10][MAXM + 10], n, m;
int f[2][1<<MAXN]; // 滚动数组 到某列时 当前答案
int g[1<<MAXN]; // 每轮列旋转1单位时的答案
map<int,int>v2mi;
int lowbit(int x) {
  return x & -x;
}
 
pair<int,int>arr[MAXM + 10];
int tmp[MAXN+10][MAXM+10];
 
void solve() {
  scanf("%d%d", &n, &m);
  int tot = (1<<n);
  rep(i,0,tot){
    f[1][i] = 0;
  }
  rep(i,0,m){
    arr[i] = {0,i};
  }
  rep(i,0,n){
    rep(j,0,m){
      scanf("%d", &a[i][j]);
      arr[j].first = max(arr[j].first, a[i][j]);
    }
  }
  sort(arr, arr + m);
  rep(j,m-min(m,n),m){
    rep(i,0,n){
      tmp[i][m-1-j] = a[i][arr[j].second];
    }
  }
  rep(i,0,n){
    rep(j,0,min(m,n)){
      a[i][j] = tmp[i][j];
    }
  }
  m = min(m,n);
 
  // f[0->i列][选的行的state] = 最大期望
  // 没有旋转的情况下
  // f[0->i列][选的行的state] = max(f[0->i-1列][选的行的stateA]+第i列选行stateB) 其中 stateA & stateB =0 , stateA|stateB = (1<<min(m,n))-1
  rep(i,0,m){
    int itr = i%2;
    rep(j,0,tot){
      f[itr][j] = 0;
    }
    // 旋转n次
    rep(j,0,n){
      rep(k,0,tot){
        g[k] = f[itr^1][k];
      }
      rep(k,0,tot){
        int p = (tot - 1)^k; // p & k =0, p|k = (tot-1)
        while( p ) {
          int x = lowbit(p);
          g[k|x] = max(g[k|x], g[k] + a[v2mi[x]][i]); // 每一圈的最值
          p -= x;
        }
      }
      // 旋转1单位
      int tmp = a[0][i];
      rep(k,0,n-1){
        a[k][i] = a[k + 1][i];
      }
      a[n - 1][i] = tmp;
 
      // 对每个state统计最大值
      rep(j,0,tot){
        f[itr][j] = max(f[itr][j], g[j]);
      }
    }
  }
  printf("%d\n", f[(m-1)%2][tot - 1]);
}
 
int main() {
  rep(i,0,MAXN){
    v2mi[1<<i] = i;
  }
  int t;
  scanf("%d", &t);
  while( t-- ){
    solve();
  }
}

本题另外一个点

max(每一行取最大值的和) = max(每一行任意取一个值的和)