Codeforces Round 554

發表於 更新於 分類於 ， Disqus： 文章字數： 710 所需閱讀時間 ≈ 2 分鐘
D (最值可达入门)

D原题

才2000分我自闭了

n(1<=n<=1000)个左括号和n个右括号组成合法括号序列

把所有合法序列来建立一个trie树

求问，给树的边上色或不上色，要求任意两个上色边不能共点，求最大上色边数

结果MOD 1e9+7

题解

首先我想到树上dp，f[当前配对数量][剩余左括号数量][是否染色边]

有关系

1
2
3
4
5
6
f[i][j][0] = max(
     f[i][j+1][1]+f[i+1][j-1][0],
     f[i][j+1][0]+f[i+1][j-1][1],
     );
f[i][j][1] =
     f[i][j+1][0]+f[i+1][j-1][0]+1;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
ll f(ll p,ll l,int pick){
  if(p==n)return pick;
  if(ret[p][l][pick] != 0)return ret[p][l][pick];
  if(l==0){ // 没有剩余左括号了，所以在树上的向下分之一定是左括号
    return ret[p][l][pick]=f(p,l+1,1-pick)+pick; // 偏序关系?
  }
  if(p+l==n){ // 左括号已经达到上限只能用右括号
    return ret[p][l][pick]=f(p+1,l-1,1-pick)+pick;// 偏序关系?
  }
  if(pick == 1){ // 当前选下面则不选
    return ret[p][l][pick]=f(p,l+1,0)+f(p+1,l-1,0)+1;// 偏序关系?
  }else{
    return ret[p][l][pick]=
      max(f(p,l+1,1)+f(p+1,l-1,0),
          f(p,l+1,0)+f(p+1,l-1,1));
  }
}

那么只要访问f(0,1,1),就可以得到答案,然后就遇到了一个问题:最大值和取模运算是冲突的

那么有什么办法可以不用比较直接直到偏序关系?

我没想出来,那么现在一个办法是偏序关系，一个办法是做高精度，还有一个办法是换方法。

来自群友梦月大佬的一句话方法:奇数层节点个数

注:按题目原型来说 最初空白节点为0层

注意每次染色一条边，如果去看树上，实际就是奇数层次的点和偶数层次的点被各染色一个，因为不同染色边不能有交点，所以边=奇数层数染色的点=偶数层数染色的点。

下面又有因为是合法对，所以从根节点到叶子节点的点数永远是偶数也就意味着每一个奇数层数的点下方一定有至少一个节点(在偶数层数)

所以边<= min(奇数层数总节点数，偶数层数总结点数) =奇数层数总结点数

下面看可达性，同上述，每个奇数节点选一个下方的偶数节点染色边，即可，保证了不会共点，又达到了奇数层数的总节点数。

综上 我们找到了一个方案达到上限，那么这个上限也就是答案了。

[至于怎么算奇数节点上总个数就无脑dp了,我想没有必要赘述了吧.