#C241101E. ARC184D-Erase Balls 2D

标签（Label）

• 动态规划

网址（Website）

[ARC184D] Erase Balls 2D - 洛谷

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

input2

3
1 3
2 1
3 2

样例输出 #1

output1

3

运算后剩余的球的可能集合是 ${1, 2, 3}$ 、 ${1, 3}$ 和 ${1, 2}$ 。

样例 #2

样例输入 #2

input2

4
4 2
2 1
3 3
1 4

样例输出 #2

output2

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）

c

#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;
}