#C241101E. ARC184D-Erase Balls 2D
标签（Label）
- 动态规划
网址（Website）
D - Erase Balls 2D (atcoder.jp)
题目（Problem）
题目描述
在二维平面上有 $N$ 个编号从 $1$ 到 $N$ 的球，第 $i$ 个位于 $(X_i, Y_i)$。其中，$X = (X_1, X_2, \cdots, X_n)$ 以及 $Y = (Y_1, Y_2, \cdots, Y_n)$ 分别是一个 $1, 2, \cdots, n$ 的排列（译注：即横纵坐标分别两两不同）。
你可以执行任意次以下操作：
- 从剩下的球中选择一个球，记为 $k$。对剩下的每个球 $i$，若满足「$X_i < X_k
$ 且 $Y_i < Y_k$」或「$X_i > X_k$ 且 $Y_i > Y_k$」（译注：即两球坐标间有二维偏序关系），将其移除。
求操作结束后，可能的剩下球的集合的数量，对 $998244353$ 取模。
输入格式
第一行输入一个数字 $N$，即球数。
之后 $N$ 行第 $i$ 行输入两个数字 $X_i$ 和 $Y_i$，即第 $i$ 个球的坐标。
输出格式
输出一个数字，代表取模后的答案。
样例 #1
样例输入 #1
3
1 3
2 1
3 2样例输出 #1
3运算后剩余的球的可能集合是 ${1, 2, 3}$ 、 ${1, 3}$ 和 ${1, 2}$ 。
样例 #2
样例输入 #2
4
4 2
2 1
3 3
1 4样例输出 #2
3限制因素
- $1 \leq N \leq 300$
- $X$ 和 $Y$ 是 $(1, 2, \dots, N)$ 的排列。
题解（Solution）
$\qquad$和那道题是一个思维，但是有点区别。
$\qquad$考虑最后会剩下什么，首先不能被删除的点一定会留下，考虑转移。
$\qquad$设 $f_i$ 表示考虑到 $y$ 坐标为 $1\sim i$ 的点的方案数。
$\qquad$如果两个点之前出现了无法删除的点，那么这两个点一定不能直接转移（否则会计算重复），否则一定可以 $[i+1,j-1]$ 中间的点都不使用删除操作。
$\qquad$直接 $O(n)$ 暴力求 $i$ ，$j$ 之间存不存在这些点，再加上枚举 $i,j$ ，总时间复杂度 $O(n^3)$ 。
代码（Code）
#include<bits/stdc++.h>
#include<vector>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int>
#define int long long
#define x first
#define y second
#define inn(x,l,r) (l<=x && x<=r)
inline int rd(){
char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;
while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x;
}const int inf = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const int N = 305;
bool ST;
inline void add(int &x,int y){if((x+=y)>=mod)x-=mod;}
inline void sub(int &x,int y){if((x-=y)<0)x+=mod;}
int n,t[N];
P a[N];
bitset<N> can;
int f[N];
void Solve(){
n=rd();For(i,1,n) a[i]={rd(),rd()}, t[a[i].y] = a[i].x;
t[0]=n+1, t[n+1]=0;
f[0] = 1;
For(i,0,n) For(j,0,i){
if(t[i+1]>t[j]) continue;
int mxx = -inf, mnx = inf;
int flag = true;
For(k,j+1,i) can[k] = false;
For(k,j+1,i) if(inn(t[k],t[i+1],t[j])){
if(t[k] < mnx) can[k] = 1;
mnx = min(mnx, t[k]);
}
Rof(k,i,j+1) if(inn(t[k],t[i+1],t[j])){
if(t[k] > mxx && can[k]) flag = false;
mxx = max(mxx, t[k]);
}if(flag) add(f[i+1],f[j]);
}printf("%lld\n", f[n+1]%mod);
}
bool ED;
signed main(){
cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
int T=1;double Tim=clock();
while(T--) Solve();
return cerr<<"TIME:"<<(clock()-Tim)/CLOCKS_PER_SEC,0;
}
