当前位置: 首页 > news >正文

35 ACwing 297 The Battle Chibi 题解

The Battle of Chibi

题面

给定一个长度为 \(N\) 的序列 \(A\) ,求 \(A\) 有多少个长度为 \(M\) 的严格递增子序列

\(1 \le M \le N \le 1000,\ |A_i| \le 10^9\)

答案对 \(10^9\) 取模

题解

\(f(i,j)\) 表示以 \(a_j\) 为结尾的长度为 \(i\) 的严格递增子序列的数量,初始 \(f(0, 0) = 1\) ,目标:\(\sum f(m,j)\)

转移

\[f(i,j) = \sum_{0 \le k < j, a_k < a_j} f(i - 1, k) \]

这个要是直接做的话时间复杂度为 \(O(N^2)\)

所以我们要想办法优化一下,因为是所有满足 \(0 \le k < j, a_k<a_j\)\(k\) ,所以可以用树状数组,\(t(a_k) = f(i - 1, k)\) ,然后在树状数组中查询即可

但是因为 \(A_i\) 的范围太大,树状数组存不下,所以要提前离散化一下,然后就可以 \(O(n \log n)\) 的进行一阶段的转移

总时间复杂度为 \(O(mn \log n)\)

code

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>using namespace std;const int N = 3e3 + 10;
const int mod = 1e9 + 7;int T, n, m, mn;
int a[N], b[N], val[N];
int t[N], f[N][N];void add (int x, int d) {while (x <= mn) {t[x] = (t[x] + d) % mod;x += x & -x;}
}int ask (int x) {int res = 0;while (x) {res = (res + t[x]) % mod;x -= x & -x;}return res;
}void solve (int id) {cin >> n >> m;mn = n;for (int i = 1; i <= n; i ++) {cin >> a[i];b[i] = a[i];}a[0] = -2e9;b[ ++ mn] = a[0];sort (b + 1, b + 1 + mn);mn = unique (b + 1, b + 1 + mn) - 1 - b;for (int i = 0; i <= n; i ++) {val[i] = lower_bound (b + 1, b + 1 + mn, a[i]) - b;}memset (f, 0, sizeof f);f[0][0] = 1;for (int i = 1; i <= m; i ++) {memset (t, 0, sizeof t);add (val[0], f[i - 1][0]);for (int j = 1; j <= n; j ++) {f[i][j] = ask (val[j] - 1);add (val[j], f[i - 1][j]);}}int res = 0;for (int i = 1; i <= n; i ++) {res = (res + f[m][i]) % mod;}printf ("Case #%d: %d\n", id, res);}int main () {cin >> T;for (int i = 1; i <= T; i ++) {solve (i);}return 0;
}
http://www.hskmm.com/?act=detail&tid=27583

相关文章:

  • 一款由网易出品的免费、低延迟、专业的远程控制软件,支持手机、平板、Mac 、PC、TV 与掌机等多设备远控电脑!
  • 计划管理
  • 苍穹外卖第二天(Nginx如何配置、MD5加密)
  • aardio跨窗口传递变量
  • AI在简单视觉推理谜题中的挑战
  • 自动引入的element-plus覆盖tailwindcss样式冲突解决方法
  • 已严肃完成今日96种状态的超级神仙DP大学习
  • P3388 【模板】割点(割顶) tarjan
  • new day
  • 10.9每日总结
  • vLLM 吞吐量优化实战:10个KV-Cache调优方法让tokens/sec翻倍
  • Linux之周期性定时任务实践
  • MyBatis-Plus 的 QueryWrapper 应用以及在内存中处理JSON数组字符串匹配
  • P9461 「EZEC-14」众数 II
  • 提升
  • 详细介绍:win11 安装 WSL2 Ubuntu 并支持远程 SSH 登录
  • Ai元人文:论智能的“全息定帧”与“渐进式显影”机制
  • 24 LCA模拟赛2T4 colorful 题解
  • 23 LCA模拟赛2T2 异或排列 题解
  • Bugkuctf的哥哥的秘密
  • 国庆做题记录(基础算法)
  • fp16训练神经网络时出现nan问题
  • 第十篇
  • 504 品酒大会!!!!!!
  • 整体理解pai0-具身智能-01 - jack
  • 【数据结构】可撤销并查集 - Slayer
  • 皮卡鱼源码导读
  • 高斯消元学习笔记
  • newDay07
  • 10月9日