Atcoder abc296

發表於 更新於 分類於 ， Disqus： 文章字數： 774 所需閱讀時間 ≈ 3 分鐘
Ex(DP)

https://atcoder.jp/contests/abc296/tasks

Ex - Unite

N行,M列, 黑/白, 至少一个黑

最小数量 把白色染成黑色, 让所有黑色是一个连通块(4临)

N 100

M 7

2s

1024mb

我的思路

这M这么小，一股插头dp/横断截面dp的味道

dp[i][横截面状态][已有不连接连通块个数:0/1] = 最小操作数

然后横截面状态, 需要保证横截面以上的内容合法， 然后状态就是最小表示法

但是这样转移太大了, 所以还是插头,

不压缩的情况 也只有$8^7=2097152$ 个状态, 而压缩后应该会很小，因为首先有从小到大性就已经$2\cdot 3\cdot 4 \cdot 5\cdot 6 \cdot 7\cdot 8=40320$, 而且相邻会属于同样的块，所以就更小的了,

O(nm state) 应该就没有了

代码

https://atcoder.jp/contests/abc296/submissions/41883375

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
99
100
101
102
103
104
105
106
107
108
109
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)(n);i++)
#define per(i,a,n) for (ll i=n;i-->(ll)(a);)

ll read(){ll r;scanf("%lld",&r);return r;}

int m;

vector<int> s2v(int state){ // state 2 vector
  vector<int> res = {};
  rep(i,0,m) {
    res.push_back(state%(m+1));
    state/=(m+1);
  }
  return res;
}

int v2s(const vector<int>&arr){ // vector 2 state
  int res = 0;
  per(i,0,m) {
    res*=(m+1);
    res+=arr[i];
  }
  return res;
}

vector<int> zip(const vector<int>&arr){
  vector<int> res(m,0);
  map<int,int> v2v;
  int k=1;
  rep(i,0,m) if(arr[i] != 0) {
    if(!v2v.count(arr[i])){
      v2v[arr[i]] = k++;
    }
    res[i] = v2v[arr[i]];
  }
  return res;
}

char s[110][10];

int main(){
  int n=read();
  m=read();
  rep(i,0,n) scanf("%s",s[i]);
  vector<int> empty(m,0);
  // dp[i][j][before block] [state] = min op
  array<map<int,int>,2> last;
  last[0][v2s(empty)] = 0;

  auto samev=[&](const vector<int>&a,int j){ // 存在 a[?] = a[j]
    rep(k,0,m) if(k!=j) if(a[k]==a[j]) return true;
    return false;
  };

  auto update=[&](map<int,int>&state,int st,int v) {
    if(!state.count(st)) state[st] = v;
    state[st]=min(state[st],v);
  };

  rep(i,0,n+1) rep(j,0,m) { // 放置[i,j], 多一行全为空复用逻辑减少判断
    int black=s[i][j] == '#'; // 空 或者'.', 填0
    array<map<int,int>,2> nstate; // new state
    rep(bf,0,2) nstate[bf]={};
    rep(bf,0,2) for(auto [st,c]: last[bf]){
      if(!black){ // 白色 且 不修改
        auto stv = s2v(st);
        if(stv[j] == 0){ // st 不变
          update(nstate[bf],st,c);
        }else{ // 非0覆盖这个位置
          if(samev(stv,j)){ // 有相同的
            stv[j] = 0;
            update(nstate[bf],v2s(zip(stv)),c);
          }else{ // 被覆盖 bf+1
            if(bf == 0){
              stv[j] = 0;
              update(nstate[bf+1],v2s(zip(stv)),c);
            }
          }
        }
      }
      // 修改0->1,或者 本来就是1
      auto stv = s2v(st);
      int top = stv[j];
      int left = j==0?0:stv[j-1];
      if(top == 0 and left == 0){ // 左上都是0
        auto tmpv = stv;
        tmpv[j] = m+1; // 单独新的连通块
        update(nstate[bf],v2s(zip(tmpv)),c+!black);
      }else if(left == 0){ // 左侧0, 上侧有值
        update(nstate[bf],st,c+!black); // 不变
      }else if(top == 0){ // 左侧有值, 上侧0
        auto tmpv = stv;
        tmpv[j] = left; // 和左侧连接
        update(nstate[bf],v2s(zip(tmpv)),c+!black);
      }else{ // 左侧上侧都有值
        auto tmpv = stv;
        rep(k,0,m) if(tmpv[k] == left) tmpv[k] = top; // 连通
        update(nstate[bf],v2s(zip(tmpv)),c+!black);
      }
    }
    rep(bf,0,2) swap(last[bf],nstate[bf]);
  }
  printf("%d\n",last[1][v2s(empty)]);
  return 0;
}

总结

Ex

很久很久很久以前学过插头dp,还就过了这个2822的红题，虽然编码速度极慢

参考

官方题解