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

题解:AT_arc184_d [ARC184D] Erase Balls 2D

题意:很简单了,不再赘述。

做法:

计数最后剩下的太麻烦,很简单的想法是记录哪些删掉了。但是感觉也不是很靠谱,因为经常来说,直接计算删掉了的那些,可能会有很多种删掉的方式最后导出了同样的结果。

先声明一种删除方案:选一个序列 \(p_1,p_2,\cdots p_k\),删掉 \(X\) 值为这些的点。

一般来说,我们考虑对这样的东西加一些限制使得删掉的和保留的一一对应,我们先考虑随意画出来一种删除方案,考虑什么样的删除方案会和他一样。

两个矩形之间有一个点删除,这里不是很方便画出来,保留的就是方格中的点。

那么考虑,如果说这些方格里存在一个点,满足对他进行操作之后仍然不变,那么完全可以再多选上他。所以我们这么加限制:对于没被选入删点集合且没有被删掉的点,他们如果被选入删点集合,那么会有更多的点被删掉。

考虑有了这个怎么计算,直接枚举最后一个选入删点集合的为 \(i\),然后枚举上一个点 \(j\),暴力扫 \([j+1,i-1]\) 的点是否满足条件即可,为了方便,我加入了 \((0,n+1),(n+1,0)\) 这两个点。

代码:

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 305, mod = 998244353;
int n, p[maxn], dp[maxn], use[maxn];
signed main() {cin >> n;p[0] = n + 1;for (int i = 1; i <= n; i++) {int x, y; cin >> x >> y;p[x] = y;}dp[0] = 1;for (int i = 1; i <= n + 1; i++) {for (int j = 0; j < i; j++) {if(p[j] < p[i])continue;int mn = p[j];for (int k = j + 1; k < i; k++)use[k] = 0;for (int k = j + 1; k < i; k++) {if(p[k] < p[i] || p[k] > p[j])continue;if(mn < p[k])use[k] = 1;elsemn = p[k];}mn = p[i];bool f = 1;for (int k = i - 1; k >= j + 1; k--) {if(p[k] < p[i] || p[k] > p[j])continue;if(mn > p[k])use[k] = 1;elsemn = p[k];f &= use[k];}dp[i] = (dp[i] + dp[j] * f) % mod;}}cout << dp[n + 1] << endl;return 0;
}
http://www.zskr.cn/news/14763.html

相关文章:

  • Chrome在Android上Speedometer性能翻倍的技术揭秘
  • OpenAI炸场!Sora 2正式发布,它不只是个视频模型,更是一个社交宇宙!
  • 格林达姆 花——季护航2006年-2017年天朝纸媒资料备份(不全)
  • velero 备份及使用方法
  • CT5132 Program. Tools for AI:-week4 note
  • Claude Code V2集成KAT-Coder
  • VMware Aria Operations 8.18.5 发布,新增功能概览
  • 20251001 之所思 - 人生如梦
  • 【Linux】库的链接与加载 - 详解
  • AGC015E Mr.Aoki Incubator
  • 动手动脑实验性问题总结
  • 深入解析:数字和字节:Linux 中的内存如何工作?
  • MySQL复合查询(重点) - 详解
  • 2025 年喷雾干燥机厂家 TOP 企业品牌推荐排行榜,无锡 / 常州喷雾干燥机 / 离心式 / 压力式 / 气流 / 造粒 / 有机溶剂 / 闭路循环 / 闭式循环 / 实验喷雾干燥机公司推荐!
  • 哈希问题的一类技巧
  • AtCoder Grand Contest 015 - E - Mr.Aoki Incubator
  • 9.30 CSP-S模拟25 改题记录
  • 完整教程:[论文阅读]Benchmarking Poisoning Attacks against Retrieval-Augmented Generation
  • 撕裂的乡土:在人性荒原上寻找微光
  • 2025 年健身器材品牌 TOP 推荐排行榜,室内 / 健身房 / 体育 / 运动 / 家用 / 商用 / 单位 / 家庭 / 有氧 / 力量健身器材推荐
  • 详细介绍:给贾维斯加“手势控制”:从原理到落地,打造多模态交互的本地智能助
  • 2025 年发泡陶瓷厂家 TOP 企业品牌推荐排行榜,发泡陶瓷线条 / 构件 / 装饰构件 / 空心砖 / 窗套线 / 浮雕 / 装饰线条推荐这十家公司
  • 2025 年传感器厂家 TOP 企业品牌推荐排行榜,磁致伸缩 / 防爆 / 防水 / 隔爆 / 线性 / 矿用 / 直线 / 油缸位移传感器 / 液位传感器公司推荐!
  • JUC:读写锁
  • 2025 年点胶机厂家 TOP 企业推荐排行榜,自动 / 果冻胶 / 无痕内衣 / 烫钻 / 珠宝热熔胶 / 水钻热熔胶 / 亮片热熔胶 / 金葱粉热熔胶点胶机推荐这十家公司!
  • 2025换热器厂家最新推荐白皮书,不锈钢 / 钛 / 哈氏合金 / 碳钢 / 衬四氟 / 列管式 / 螺旋板 / 管壳式 / 缠绕式 / 复合材料换热器公司推荐!
  • IELTS-G Writing Task1 informal letters
  • 2025 年 AI 教育培训机构推荐及选择指南:企业 AI 教育培训 / AI + 教育 / AI 教育线下机构 / AI 企业教育培训机构 / AIGC 教育培训推荐这五家公司!
  • 社区互助养老框架|基于java和小程序的社区互助养老系统小程序设计与实现(源码+数据库+文档)
  • oppoR9m刷Linux系统: 电脑安装驱动工具