当前位置: 首页 > 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.hskmm.com/?act=detail&tid=22601

相关文章:

  • US$39 PowerBox for KTM JTAG for Hitachi
  • 最小二乘问题详解2:线性最小二乘求解
  • OpenAI炸场!Sora 2正式发布,它不只是个视频模型,更是一个社交宇宙!
  • 基于python资料挖据的教学监控系统的设计与应用
  • 2025防腐木厂家权威推荐榜:实力品牌与定制服务深度解析
  • 中间件详解与自定义 - 实践
  • 格林达姆 花——季护航2006年-2017年天朝纸媒资料备份(不全)
  • 【Groovy】变量和基本数据类型
  • 2026届模拟/射频IC设计方向保研经验分享
  • 2021 ICPC 沈阳 BEFHJLM(待补
  • Docker容器完全操控指南
  • 【Groovy】Groovy环境搭建
  • 2025年TAB拉链制造商权威推荐榜:创新设计与耐用品质口碑
  • 变量类型
  • 10.1
  • VMware Cloud Foundation 9.0.1.0 发布 - 领先的多云平台
  • velero 备份及使用方法
  • 洛谷月赛T1 P14081 「CZOI-R7」炸弹游戏
  • VMware NSX 4.2.3.1 发布,新增功能概览
  • Claude Code V2集成KAT-Coder
  • Ubuntu 软件源
  • Ceph 分布式存储学习笔记(一):介绍、部署与集群设置(上)
  • 数学学习总结
  • VMware Aria Suite Lifecycle 8.18 Patch 5 发布,新增功能概览
  • P3977 [TJOI2015] 棋盘题解
  • 03. 基本元素
  • 基础整理01:Bode图、PM、GM、极点零点 - 教程
  • [已解决]CUDA error: CUBLAS_STATUS_EXECUTION_FAILED when calling cublasSgemmStridedBatched
  • VMware vCenter Server 7.0U3w 发布 - 集中管理 vSphere 环境
  • VMware Aria Operations 8.18.5 发布,新增功能概览