2021 牛客多校第二场 G.League of Legends @ Wings            分类 ACM
发布于 星期三, 八月 4 日, 2021 年
更新于 星期四, 八月 12 日, 2021 年

题目

题意

$n$ 个区间 $[l_i, r_i)$, 分成 $m$ 组, 要求一组里的区间交集不为空. 一组的贡献是这组里区间交集的大小. 问最大贡献.

$1 \le m \le n \le 5000, 0 \le l_i < r_i \le 10^5$

题解

贪心是错的, 又难写又过不了, 自闭了

首先把包含了其他区间的区间提出来, 这些区间只要不独立成组, 那么组的贡献就和它没有关系了.

既然不是贪心, 那么考虑 dp, 对剩下来的区间做dp. 设 $dp(i, j)$ 为前 $i$ 个分成 $j$ 组的最大总贡献, 转移如下:

$$dp(i, j) = \max_{k < i} \{ dp(k, j-1) + \min_{k < x \le i} \{r_x\} - \max_{k < y \le i} \{ l_y \} \}$$

且需要满足 $\min_{k < x \le i} \{r_x\} > \max_{k < y \le i} \{ l_y \}$

把剩下来的区间按先 $l$ 后 $r$ 排个序, 会发现这些区间的 $l$ 和 $r$ 分别递增, 式中的 $\min_{k < x \le i} \{r_x\} = r_{k+1}, \max_{k < y \le i} \{ l_y \} = l_i$. 方程变为:

$$dp(i, j) = \max_{k < i} \{ dp(k, j-1) + r_{k+1} - l_i \}$$

$l_i$ 提出来:

$$dp(i, j) = \max_{k < i} \{ dp(k, j-1) + r_{k+1} \} - l_i$$

朴素转移 $O(n^3)$, $\max_{k < i} \{ dp(k, j-1) + r_{k+1} \}$ 这个东西可以用单调队列来优化, 而且是常见的限制转移且限制单调, 即 $r_{k+1}$ 需要大于 $l_i$, 而限制 $l_i$ 和条件 $r_{i+1}$ 都是递增的. 那么对每个 $j-1$, 维护一个 $dp(k, j-1) + r_{k+1}$ 单调递减的双端单调队列, 从队头开始判断是否满足限制, 不满足就弹出, 否则就是满足限制的最优决策. 注意维护的是 $j-1$ 的队列, 和当前转移的 $j$ 的没有关系, 只不过是因为做到了 $i$, 以后的都可以考虑 $i$, 所以要把 $dp(i, j-1)$ 放进去. 从队首放, 先判断队首 $dp(k, j-1) + r_{k+1}$ 和 $dp(i, j-1), r_{i+1}$ 的大小, 如果前者小, 说明它一定不会是最优决策点, 弹出. 继续判断, 直到不满足, 再压入 $i$ 决策点.

还有一点细节, 当 $i < j$ 时 $dp(i, j)$ 不存在, 可以设为负无穷, 转移的时候也不要用它转移, 双重保险. 也就是说, 先枚举 $j$ 再枚举 $i$ 时, 直接从 $j$ 开始就行了, 再小的是不存在的状态. 需要注意, $j-1$ 队列中是有 $j-1$ 的, 这应该是第一个点, 往后加入的决策点因为这样的枚举, 都是不小于 $j$ 的, 要注意在开头压入 $j-1$.

大概总结一下关于多个区间的题

  1. 如果区间都是包含关系而没有相交关系, 那么区间的包含关系是一棵树, 按先 $l$ 递增后 $r$ 递减排序后是树的前序遍历, 可维护栈来构造这棵树. (见OpenCup某题)
  2. 如果把包含的大区间去掉, 剩下的区间按先 $l$ 后 $r$ 排序, 那么 $l$, $r$ 分别递增(本题)
代码
int n, k, L[MAXN], R[MAXN];
vector<PII> a, b, c;
bool big[MAXN];
LL dp[MAXN][MAXN], w[MAXN];

bool cmp(PII &p, PII q) {
  auto[lp, rp] = p;
  auto[lq, rq] = q;
  return rp - lp > rq - lq;
}

int main() {
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= n; i++) {
    int l, r;
    scanf("%d%d", &l, &r);
    a.emplace_back(l, r);
  }

  for (int i = 0; i < n; i++) if (!big[i]) {
    auto[li, ri] = a[i];
    for (int j = 0; j < n; j++) if (j != i && !big[j]) {
      auto[lj, rj] = a[j];
      if (li == lj && ri == rj)
        big[j] = 1;
    }
  }

  for (int i = 0; i < n; i++) if (!big[i]) {
    auto[li, ri] = a[i];
    for (int j = i+1; j < n; j++) if (!big[j]) {
      auto[lj, rj] = a[j];
      if (lj <= li && ri <= rj)
        big[j] = 1;
      if (li <= lj && rj <= ri)
        big[i] = 1;
    }
  }

  for (int i = 0; i < n; i++) {
    if (big[i])
      b.push_back(a[i]);
    else
      c.push_back(a[i]);
  }

  int m = c.size();
  c.emplace_back(0, 0);
  sort(c.begin(), c.end());
  for (int i = 1; i <= m; i++) {
    auto[l, r] = c[i];
    L[i] = l, R[i] = r;
  }

  sort(b.begin(), b.end(), cmp);
  for (int i = 1; i <= n-m; i++) {
    auto[l, r] = b[i-1];
    w[i] = w[i-1] + r - l;
  }

  for (int i = 0; i <= m; i++)
    for (int j = 0; j <= k; j++)
      dp[i][j] = -INF;

  dp[0][0] = 0;
  deque<int> Q;
  for (int j = 1; j <= min(m, k); j++) {
    Q.clear();
    Q.push_back(j-1);
    for (int i = j; i <= m; i++) {
      while (Q.size() && R[Q.front()+1] <= L[i])
        Q.pop_front();
      if (Q.size())
        dp[i][j] = dp[Q.front()][j-1] + R[Q.front()+1] - L[i];
      while (Q.size() && dp[Q.back()][j-1] + R[Q.back()+1] <= dp[i][j-1] + R[i+1])
        Q.pop_back();
      Q.push_back(i);
    }
  }
  LL ans = -INF;
  for (int i = 1; i <= min(m, k); i++)
    ans = max(ans, dp[m][i] + w[k-i]);

  printf("%lld\n", max(0ll, ans));

  return 0;
}

留下昵称和邮箱, 可在第一时间获悉回复通知哦~

2021 FLAG

  • 找个妹子
  • 进计科
  • XCPC拿块金牌
  • 补全算法知识, 整全板子
  • 学会Web开发相关知识
  • 在服务器上搭建电子书库
  • 写个游戏并上线
  • 能弹一首曲子
  • 写首完整的曲子
  • 练习悠悠球

个人简介

我叫 Wings, 来自江西上饶, 目前人在西安, 是西电的一名学生.

常以 WingsWingsZengWingsWings的ID在各大小网站上游走, 一般来说, Wings不是我 😔, WingsZeng 一定是我 😊.

热爱算法, 喜欢钻研各种计算机技术.

业余爱好广泛, 只要不是文化课基本上都感兴趣😏.

开发/项目经历

  1. Android游戏 小墨滴的复仇 (弃坑)
  2. Android游戏 Circle Run (弃坑)
  3. Windows游戏 Snague (可能弃坑了吧)
  4. Python后端 Fathy' (可能弃坑了吧)

to be continued

教育经历

时间 学历 学校
2008-2014 小学 上饶市第十二小学
2014-2017 初中 上饶市第四中学
2017-2020 高中 上饶市第一中学
2020-2024 本科 西安电子科技大学
to be continued

比赛/竞赛经历

太久远太小的记不到了…

  1. 2017 国学竞赛初赛江西 没有分数或排名 二乙
  2. 2018 NOIP提高 258 省二
  3. 2019 CSP-S江西专场 145 省二
  4. 2019 数学竞赛初赛 70 没排名 (复赛打铁qaq)
  5. 2020 Gitee|Python贪吃蛇魔改大赛 可能是第四? 二等奖
  6. 2020 西电ACM训练基地熊猫杯 第四 银牌
  7. 2020 西安三校微软学生俱乐部Hackathon 和二等奖最后一名差0.5分 三等奖
  8. 2020 西电星火杯 三等奖
  9. 2020 西电ACM新生赛 第九 金牌
  10. 2020 ICPC 亚洲区域赛 济南站 132名 铜牌
  11. 2020-2021 第二届全国大学生算法设计与编程挑战赛(冬季赛) 924名 铜牌 (别骂了别骂了)
  12. 2020 ICPC 亚洲区域赛 昆明站 打星
  13. 2020 ICPC Asia-East Continent Final 签完到溜 打铁
  14. 西电"智能星"第一届自动驾驶小车比赛 第五 优胜奖|极速奖 本来可以冠军的别骂了别骂了
  15. 2021团体程序设计天体赛(CCCC) 个人二等奖
  16. 2021 西电 miniL CTF 优胜奖
  17. 2021 西电ACM校赛 第9名 金牌
  18. 2021 西电数模校赛 二等奖
  19. 2021 第15届IEEE 第48名
  20. 2021 CCPC 桂林站 打星

to be continued

爱好

技术

  • 算法
  • 独立游戏开发

游戏

  • Minecraft
  • Black Survival
  • I Wanna
  • Celeste
  • Life is Strange
  • Need for speed

运动

  • 篮球
  • 桌球
  • 乒乓球
  • 羽毛球
  • 慢跑

音乐

  • 吉他
  • 词曲
  • 流行

玩具

  • 魔方
    • 三阶速拧
    • 三阶盲拧
    • 高阶
  • yoyo球

追星

  • VAE
  • Benedict Cumberbatch