Codeforces Round 584 - Dasha Code Championship - Elimination Round

發表於 2019-09-16 更新於 2025-06-05 分類於 Codeforces ， Div1+2 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

#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(每一行任意取一个值的和)

Educational Codeforces Round 72

發表於 2019-09-06 更新於 2025-06-05 分類於 Codeforces ， Edu Disqus：文章字數： 1.3k 所需閱讀時間 ≈ 4 分鐘

E (线段树 + 常数优化)

原题链接

大意

n个数 a[1->n]

m 个询问

询问类型1: 改动指定下标i的值为x

询问类型2: 求下标a[l->r] 区间上是否存在两个数 ,使得十进制表示的数在数位上有同时不为0的,如果有求和最小的两个数，否则输出-1

例如 10010 和 23 在第2位一个是1,一个是2不同时为0,他们的和就正常加法10010+23=10033

例如 10101 和 1010 ，就不满足要找的数

求的是，满足的数的最小和

注:原题没有这么直接，这是一眼看出的原体的本体

数据范围

0<a[i]<=1'000'000'000

0<=n,m<=200'000

题解

一眼题解就是

按十进制分割成 10个线段树，第i个线段树上只留在十进制第i位不为0的

线段树修改和查询也就线段树日常操作

第一份代码 WA2了,问题出在 ++soo.begin() 写成soo.begin()++了,用的下标-1记录个数有点问题改成0x3f3f3f3f

第二份代码 MLE5，问题在不需要维护所有，只需要维护最小两个数

第三份代码 TLE5

第四份代码依然TLE5，相对于第三份代码的改动

我把pair<int,int>等换成了数组，感觉这样也许更快,也许不
很重要的一个改动sort()调用换成冒泡,因为才4个，然后我本地生成随机数测试，就初始化线段树的时间，明显从2秒多变为1秒上下

1762ms AC代码我对初始化进行优化把一个一个insert改成递归build，初始化时间变到了0.1s左右然后ac

AC代码

#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);
 
// 没有进位,其余是0
 
// 按十进制 线段树 +multiset
 
struct SEGT{
  int cnt;
  int vs[2];
}segt[12][800010];
#define UNSETINF -1
int a[200010];
int n,q;
 
// template<typename... Args>
// void ptf(const char* fmt, Args... args ){
//   return ;
//   printf(fmt,args...);
// }
 
void mergeS(int *v1,int *v2,int *outv){
  unsigned int sa[] = {
    (unsigned int)v1[0],
    (unsigned int)v1[1],
    (unsigned int)v2[0],
    (unsigned int)v2[1]
  };
  rep(i,0,2){
    rep(j,i+1,4){
      if(sa[j] < sa[i]){
        swap(sa[i],sa[j]);
      }
    }
  }
  // sort(sa,sa+4);
  outv[0] = sa[0];
  outv[1] = sa[1];
}
 
void insert(int off,int o,int l,int r,int idx,int v){
  segt[off][o].cnt++;
  if(l == r){
    segt[off][o].vs[0] = v;
    return ;
  }
  int mid = (l+r)/2;
  if(idx <= mid){
    insert(off,o<<1,l,mid,idx,v);
  }else{
    insert(off,o<<1 | 1,mid+1,r,idx,v);
  }
  mergeS(segt[off][o<<1].vs,segt[off][o<<1|1].vs,segt[off][o].vs);
}
static int ten[]={1,10,100,1'000,10'000,100'000,1'000'000,10'000'000,100'000'000,1'000'000'000};
 
void build(int off,int o,int l,int r){
  if(l == r){
    if((a[l] / ten[off])%10 != 0){
      segt[off][o].vs[0] = a[l];
      segt[off][o].cnt++;
    }
    return ;
  }
  int mid = (l+r)/2;
  build(off,o<<1,l,mid);
  build(off,o<<1|1,mid+1,r);
  mergeS(segt[off][o<<1].vs,segt[off][o<<1|1].vs,segt[off][o].vs);
  segt[off][o].cnt = segt[off][o<<1].cnt + segt[off][o<<1|1].cnt;
}
 
void del(int off,int o,int l,int r,int idx,int v){
  // ptf("del _%d_ o[%d] [%d -> %d] , [%d] = %d\n",off,o,l,r,idx,v);
  segt[off][o].cnt--;
  if(l == r){
    segt[off][o].vs[0] = UNSETINF;
    return ;
  }
  int mid = (l+r)/2;
  if(idx <= mid){
    del(off,o<<1,l,mid,idx,v);
  }else{
    del(off,o<<1 | 1,mid+1,r,idx,v);
  }
  mergeS(segt[off][o<<1].vs,segt[off][o<<1|1].vs,segt[off][o].vs);
}
 
void change(int idx,int v){
  int oldv = a[idx];
  if(oldv == v)return;
  rep(j,0,10){
    if(oldv%10 != 0){
      del(j,1,0,n-1,idx,a[idx]);
    }
    oldv/=10;
  }
  a[idx] = v;
  rep(j,0,10){
    if(v%10 != 0){
      insert(j,1,0,n-1,idx,a[idx]);
    }
    v/=10;
  }
}
 
void qtree(int off,int o,int l,int r,int ql,int qr,int *ret){
  // ptf("qtree  _%d_ o[%d] [%d -> %d] , [%d -> %d] \n",off,o,l,r,ql,qr);
  if(segt[off][o].cnt == 0){
    ret[0] = UNSETINF;
    ret[1] = UNSETINF;
    // ptf("qtree  _%d_ o[%d] [%d -> %d] , [%d -> %d]",off,o,l,r,ql,qr);
    // ptf("\t 1pret [%d %d]\n",ret[0],ret[1]);
    return ;
  }
  if(l == ql && r == qr){
    ret[0] = segt[off][o].vs[0];
    ret[1] = segt[off][o].vs[1];
    // ptf("qtree  _%d_ o[%d] [%d -> %d] , [%d -> %d]",off,o,l,r,ql,qr);
    // ptf("\t 2pret [%d %d]\n",ret[0],ret[1]);
    return ;
  }
  int mid = (l+r)/2;
  if(qr <= mid){
    qtree(off,o<<1,l,mid,ql,qr,ret);
    return ;
  }else if(ql > mid){
    qtree(off,o<<1 | 1,mid+1,r,ql,qr,ret);
    return ;
  }
  int retl[2];
  qtree(off,o<<1    ,l    ,mid,ql   ,mid,retl);
  int retr[2];
  qtree(off,o<<1 | 1,mid+1,r  ,mid+1,qr,retr);
  mergeS(retl,retr,ret);
}
 
void query(int l,int r){
  int ans = -1;
  rep(j,0,10){
    int ret[2];
    qtree(j,1,0,n-1,l,r,ret);
    if(ret[1] == -1){
      continue;
    }
    if(ans == -1 || ans > ret[0]+ret[1]){
      ans = ret[0]+ret[1];
    }
  }
  printf("%d\n",ans);
}
 
void init(){
  rep(i,0,11){
    rep(j,0,800001){
      segt[i][j].vs[0] = UNSETINF;
      segt[i][j].vs[1] = UNSETINF;
    }
  }
}
 
int main(){
  init();
  scanf("%d %d",&n,&q);
  rep(i,0,n){
    scanf("%d",a+i);
  }
  rep(off,0,10){
    build(off,1,0,n-1);
  }
  rep(i,0,q){
    int op;
    scanf("%d",&op);
    if(op == 1){
      int idx,x;
      scanf("%d %d",&idx,&x);
      change(idx-1,x);
    }else{
      int l,r;
      scanf("%d %d",&l,&r);
      query(l-1,r-1);
    }
  }
  return 0;
}

后记

后续优化

把冒泡改成了if
去掉了计数和cnt =0 判断 (因为考虑到更多的情况来说不为0 吗?)

时间来到了1372 ms, 有400ms左右的优化效果但是RUSH_D_CAT的代码的代码只要900+ms,

那么感觉可能的影响

是函数传参个数,涉及到汇编指令个数?
我看他的分段处理是每层都处理，而我的是在最外层 for 0->9,所以可能的是连续内存访问带来的cache 高性能?

Codeforces Round 581

發表於 2019-08-23 更新於 2025-06-05 分類於 Codeforces ， Div2 Disqus：文章字數： 507 所需閱讀時間 ≈ 2 分鐘

E (DP + 组合数学)

原题链接

又是一个大家都会的组合数学，就我不会

本题目2400评分

大意

列出n个1 m个-1的所有排列

求(每个排列的最大前缀和(>=0))的和

数据范围

0<=n,m<=2000

题解

注翻译自官方题解

k[x][y] 表示由 x个1 和y个-1组成的最大前缀和为0的数组个数

k[0][y] = 1 显然只有一种情况

k[x][y] = 0 (if x>y)

k[x][y] = k[x-1][y] + k[x][y-1]

关于上面的转移

从是最后增加一个数字转移进行考虑，分别讨论最后一位是1或-1,

1的情况，由x<=y得最大前缀和不会超过0

-1的情况，明显了增加负1不会影响前缀和

然后

dp[x][y]为方案数则 dp[n][m]为答案

dp[0][y] = 0 显然

dp[x][0] = x 显然

否则

$d[x][y] = (\binom{x+y-1}{y}+d[x-1][y]) + (d[x][y-1] - (\binom{x+y-1}{x}-k[x][y-1]))$

解释:分类首位是1或-1讨论

首位是1 剩余部分的方案数是如下组合数，对于每个方案的最大前缀和都+1了,除了首位的部分是d[x-1][y]

$\binom{x+y-1}{y} + d[x-1][y]$

首位是-1, 剩余部分的方案数是如下组合数，但并不是对于每个方案的最大前缀和都-1了，只有那些最大前缀和>0的才会影响,所以是 -1* (组合数 - (最大前缀和为0的个数)),除了首位的部分是d[x][y-1]

$d[x][y-1] - ( \binom{x+y-1}{x}-k[x][y-1])$

实现

没有代码！

上面算法知道了，那么还剩下

递推,for一下
MOD运算别忘了
组合数(才2k随便搞),乘法逆元 O(n) 或者组合数递推关系(高中知识) O(n^2),不过看递推基本都要算到，直接无脑递推就好了

参考

https://codeforces.com/blog/entry/69244

Educational Codeforces Round 70

發表於 2019-08-12 更新於 2025-06-05 分類於 Codeforces ， Edu Disqus：文章字數： 1.3k 所需閱讀時間 ≈ 4 分鐘

E(AC自动机(Aho–Corasick automaton))

E

原题链接

大家都会ac自动机就我不会

本题目2500评分

大意

字符串$t$

和长$n$字符串列表 $s$

对于所有$(i,j)$, 求s[i]+s[j]在t中的出现次数的和

数据范围

$|t|\le 200’000$

$n \le 200’000$

$|s_i| \in [1,200’000]$

$\sum |s_i| \le 200’000$

题解

显然

$ans = \sum \mathrm{suffix}i \cdot \mathrm{prefix}{i+1}$ 也就是以$i$结尾匹配到的次数乘上$i+1$为开头匹配到的次数

那么问题来了，如何计算成功匹配的次数

引理 Aho–Corasick automaton

前置知识: Trie树, KMP

AC自动机是什么?

答: ~~一种算法可以自动AC所有题目~~,多个模式同时匹配

AC自动机从数据结构上看起来是个什么？

Trie Tree(字典树) + 匹配失败时的目标跳转指针(仿照KMP)

trie tree and fail

对于字典建立的自动机

a
ab
bab
bc
bca
c
caa

其中后缀链接(suffix links/fail边)为蓝色, 字典后缀链接(dictionary suffix links)为绿色, 字典项为高亮蓝圆

建立Trie树

节点内容

map<char,Node*> next 黑色边
cnt 蓝色圆(条目计数)
dep 长度/高度
fail 仿照kmp失配边, 绿色边
last 后缀链接 蓝色边

在建立过程中，结束的位置计数cnt++ (蓝色圆)

记录深度dep

计算next

建立 fail边

fail边的意义, 这来自于kmp中的fail, 假设当前为s, 则是指向s的最长后缀, 且为某个模式的前缀

s: ????abcde
           |
           |
           v
t:     abcde 且t是某个最长前缀

默认值为所有fail边指向根节点

按深度(dep)从小到大广搜，

第一层节点的fail都指向根节点(一个字符更短的只有空字符串

每个节点的子节点扩展

p->next[charX] = p->fail->next[charX]

如果p->fail的后续节点没有charX呢? 实际上会递归fail(p->fail->fail->next[charX]),去找首个有charX的(和kmp里的一样)

匹配字符串

当建立完fail边就可以拿来匹配字符串了, 每次失去匹配通过fail进行跳转

建立last边

如何计数当有 abba和bb的时候，如何能计数到bb?

每个节点增加一个last，指向 dep小于该节点的，存在的是该字串后缀的末节点。

1
2
3

root-a-b-b-a
    \
     b-b

这样的情况下，需要一条last，从a-b-b指向b-b的后一个b,其余节点的last指向根节点

所有last默认指向根节点

要是某个后缀，那么cnt>0,又要小于该字符串的最长的

则 ->fail(当->fail->cnt >0) 或->fail->last(->fail->cnt ==0 )

这样增加了last指针后，在匹配时，如果当前链下是后缀，则开始计数，如果不是则从当前->last开始计数

换句话说, last的本质是把fail链上中间的cnt==0的点移除了, 只留了cnt>0的点和起始节点

递归代价? 复杂度分析?

fail边

不妨把fail 指针看到它指向的dep, 那么在树上, 显然每个点要么比它父节点指向的dep大1, 要么比父节点小, 每个从根到叶子的相邻变化和非负,且小于链长度, 正变化+|负变化| <= 2长度, 所以所有变化次数和 <= 2所有t的长度和, 和O(trie)建树一样的复杂度

当每层节点较少，比如只包含所有小写字母时，可以增加每层节点优化掉这递归过程

last边

很显然每个点操作代价为常数所以O(点 < sum |字典|)

代码

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
typedef long long ll;
const int MAX = 2e5+10;
struct AC_Automaton {
  static const int K=26;//may need change
  static const int MAX_NODE=2e5+10;
  int getid(char c) {//may need change
    return c-'a';
  }
  struct AC_NODE{
    AC_NODE * next[K];
    AC_NODE * fail;
    AC_NODE * last;
    int cnt;
    int dep;
    void init(AC_NODE * ac_n){
      rep(i,0,K){
        next[i] = ac_n;
      }
      fail = ac_n;
      last = ac_n;
      cnt = 0;
      dep = 0;
    }
  }nodes[MAX_NODE];
  AC_NODE * root;
  int tot;
  AC_NODE * newnode() {
    nodes[tot].init(&nodes[0]);
    return &nodes[tot++];
  }
  void init() {
    tot=0;
    root=newnode();
  }
  void insert(char *s) {
    AC_NODE * now = root;
    int len=strlen(s);
    rep(i,0,len){
      int t=getid(s[i]);
      if(now->next[t] == root) {
        now->next[t] = newnode();
        now->next[t]->dep = i+1;
      }
      now=now->next[t];
    }
    now->cnt++;
  }
  void setfail() {
    queue<AC_NODE *>q;
    rep(i,0,K){
      if(root->next[i] != root){
        q.push(root->next[i]);
      }
    }
    while(!q.empty()){
      AC_NODE * now=q.front();
      q.pop();
      //suffix link
      now->last = now->fail->cnt > 0 ? now->fail : now->fail->last;
      rep(i,0,K){
        if(now->next[i] != root) {
          now->next[i]->fail=now->fail->next[i];
          q.push(now->next[i]);
        }else{
          now->next[i]=now->fail->next[i];
        }
      }
    }
  }
  ll be[MAX],en[MAX];
  void work(char *s) {
    int n = strlen(s);
    AC_NODE * now = root;
    rep(i,0,n+1){
      be[i]=en[i]=0;
    }
    rep(i,0,n){
      now=now->next[getid(s[i])];
      AC_NODE * tmp = root;
      if(now->cnt){
        tmp=now;
      }else if(now->last->cnt){
        tmp=now->last;
      }
      while(tmp != root){
        en[i]+=tmp->cnt;
        if(i-tmp->dep+1>=0){
          be[i-tmp->dep+1]+=tmp->cnt;
        }
        tmp=tmp->last;
      }
    }
    ll ans=0;
    rep(i,0,n-1){
      ans+=en[i]*be[i+1];
    }
    printf("%lld\n",ans);
  }
}ac;
char s[MAX],tmp[MAX];
int main() {
  int q;
  scanf("%s",s);
  ac.init();
  scanf("%d",&q);
  while(q--) {
    scanf("%s",tmp);
    ac.insert(tmp);
  }
  ac.setfail();
  ac.work(s);
  return 0;
}

参考

https://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_algorithm

https://oi-wiki.org/string/ac-automaton/

TODO 抽个板子

Codeforces Round 576

發表於 2019-07-31 更新於 2025-06-05 分類於 Codeforces ， Div1 Disqus：文章字數： 869 所需閱讀時間 ≈ 3 分鐘

D (DP)

D

原题链接

大意

n*n正方形有黑有白

每次可以选择一个矩形把它全变成白色，代价是max(长,宽)

求吧整个正方形全变白的最小代价

数据范围

n <= 50

题解

首先如果我们刷了两个有相邻边或重叠的白色矩形

那么假设他们的代价分别为 x和y

那么一定有一个变长为x+y的正方形完全覆盖了这两个白色矩形

dis|row| <= rowX+roxY <= costX+costY = x+y

dis|col| <= colX+roxY <= costX+costY = x+y

所以综上所述两两不重叠

再来，证明如果最优结果要么选择的单一矩形，要么一定能垂直或水平分化,即是不会出现类似弦图这样的分化

假设存在，那么意味这有n*m的矩形，和对应选择多个图画方案，使得

图画方案是最优的
子选择矩形个数大于1
不存在按竖着分化,或横着分化，使得子选择被分开

对于横向来看，意味着任意选择分割线都会和最优解的选择中的矩形的横着的边冲突，

也就意味着，从min横向点到 max横向点，所有点都有边。

即是，从横向看最优解的 cost 横向 >= (max横向点-min横向点)

由对称性，从纵向看最优解的 cost 纵向 >= (max纵向-min纵向点)

那么我们直接用相应的大矩形(max横向点-min横向点,max纵向-min纵向点) 从面积上覆盖最优解答

即

大矩形 cost (从覆盖关系，和最优解答定义)>= 最优解答cost (根据横向和纵向边的关系)>= 大矩形cost

综上

没有重叠至多相邻
要么单一选择的矩形(如大矩形)，要么可纵向或可横向分割

所以

dp[top i0 -> bottom i1][left j0 -> right j1]
=min(
  max(i1-i0,j1-j0),
  dp[i0 -> k][j0->j1] + dp[k+1->i1][j0->j1],
  dp[i0 -> i1][j0 -> k] + dp[i0->i1][k+1->j1],
)

时间复杂度 O(枚举长 * 枚举宽 * 枚举左上角坐标 * 状态转移) = O(n * n * (n * n) * n) = O(n^5)

能过

代码 Rust

920ms/1s 强行过了,慢应该是用Vec的原因,如果换成c++的直接数组的话，应该能快很多，// 我暂时还没玩会Rust的多维数组

CODE URL

#![allow(unused_imports)]
use std::cmp::*;
use std::collections::*;

struct Scanner {
   buffer : std::collections::VecDeque<String>
}

impl Scanner {

   fn new() -> Scanner {
      Scanner {
         buffer: std::collections::VecDeque::new()
      }
   }

   fn next<T : std::str::FromStr >(&mut self) -> T {

      if self.buffer.len() == 0 {
         let mut input = String::new();
         std::io::stdin().read_line(&mut input).ok();
         for word in input.split_whitespace() {
            self.buffer.push_back(word.to_string())
         }
      }

      let front = self.buffer.pop_front().unwrap();
      front.parse::<T>().ok().unwrap()
   }
}

fn main() {
    let mut s = Scanner::new();
    let n : usize = s.next();
    // dp[top i][left j][bottom i][right j] 全部清理 需要的最小代价
    let mut dp = vec![vec![vec![vec![0;n+1];n+1];n+1];n+1];
    for i in 0..n {
        let line:String = s.next();
        for (j, ch) in line.chars().enumerate() {
            if ch == '#' {
                dp[i][j][i][j] = 1;
            }
        }
    }
    // 枚举 矩形大小从小到大
    for i in 0..n {
        for j in 0..n {
            if i == 0 && j == 0 {
                continue;
            }
            // 枚举 矩形左上角坐标
            for p in 0..n-i {
                for q in 0..n-j {
                    // 右下角坐标
                    let (x,y) = (i+p,j+q);
                    dp[p][q][x][y] = max(i,j)+1;
                    for k in p..x {
                        dp[p][q][x][y]=min(dp[p][q][x][y],dp[p][q][k][y]+dp[k+1][q][x][y]);
                    }
                    for k in q..y {
                        dp[p][q][x][y]=min(dp[p][q][x][y],dp[p][q][x][k]+dp[p][k+1][x][y]);
                    }
                }
            }
        }
    }
    println!("{}",dp[0][0][n-1][n-1]);
}