ARC184D Erase Balls 2D 题解

将所有球按照

X_i

排序，那么第

i

个球满足

X_i=i

。显然选择的球的顺序并不重要，我们只需要明确哪些球被选了。为了方便，我们在

(0,n+1)

和

(n+1,0)

处各添加一个球，并强制选择这两个球。

设选择的球所组成的集合为

S=\{a_1,a_2,\dots,a_m\}\ (0=a_1 \lt a_2 \lt \dots \lt a_m=n+1)

，那么显然有

Y_{a_1}\gt Y_{a_2}\gt \dots \gt Y_{a_m}

。

设剩余的球所组成的集合为

f(S)

：

对于 $u \in f(S)$ 且 $x \not\in f(S)$ ，设 $a_j \lt u \lt a_{j+1}$ ，则显然有 $Y_{a_j}\gt Y_u \gt Y_{a_{j+1}}$ ；
对于 $v \not\in f(S)$ ，设 $a_j \lt v \lt a_{j+1}$ ，则显然有 $Y_{a_j} \lt Y_v$ 或 $Y_v \lt Y_{a_{j+1}}$ 。

直接对本质不同的

f(S)

进行计数比较困难，因此可以转化计数对象，对选择的球所组成的集合

S

进行计数。

显然不漏容易做到，于是问题变成了如何做到不重。考虑把

f(S)

的贡献转化到满足下列条件的集合

T

上：

$f(T)=f(S)$ ；
对于任意 $u \not\in T$ ， $f\big(\{u\} \cup T\big) \ne f(S)$ ；换句话说，即再选择任意一个球都会导致 $f(T)$ 变化。

显然满足条件的集合

T

是唯一的，因为了第二个条件相当于要求了集合

T

是极大的。

于是现在只需要统计有多少个集合

T

满足上面的条件即可。设

f_i

表示考虑完前

i

个球且选择了第

i

个球的满足条件的集合

T

的数量。转移时枚举

0 \le j \lt i

且

Y_j \gt Y_i

的整数

j

，表示上一个选择的球为

j

，判断是否能从

j

转移到

i

：

若存在 $j \lt k \lt i$ ，使得对于任意 $j \lt u \lt k$ 都不满足 $Y_i \lt Y_u \lt Y_k$ 且对于任意 $k \lt v \lt i$ 都不满足 $Y_k \lt Y_v \lt Y_j$ （即选择 $k$ 不会导致 $f(T)$ 变化），则不能从 $j$ 转移到 $i$ ，否则可以从 $j$ 转移到 $i$ 。

于是做一个二维前缀和即可

\mathcal O(n)

检验是否能从

j

转移到

i

。总时间复杂度

\mathcal O(n^3)

。

const int N=305,mod=998244353;
int n,v[N],s[N][N],f[N];
void add(int &a,int b){
	a+=b;
	if(a>=mod) a-=mod;
}
bool check(int ax,int ay,int bx,int by){
	return s[ax][ay]-s[ax][by-1]-s[bx-1][ay]+s[bx-1][by-1]==1;
}
void solve(){
	cin>>n,s[1][n+2]++,s[n+2][1]++,v[1]=n+2,v[n+2]=1;
	for(int i=1,x,y;i<=n;i++) cin>>x>>y,x++,y++,v[x]=y,s[x][y]++;
	for(int x=1;x<=n+2;x++) for(int y=1;y<=n+2;y++) s[x][y]=s[x][y]+s[x-1][y]+s[x][y-1]-s[x-1][y-1];
	f[1]=1;
	for(int i=2;i<=n+2;i++){
		for(int j=i-1;j>=1;j--){
			if(v[j]<v[i]) continue; 
			bool flag=1;
			for(int k=j+1;k<i;k++){
				if(check(k,v[k],j,v[i])&&check(i,v[j],k,v[k])){
					flag=0;
					break;
				}
			}
			if(flag) add(f[i],f[j]);
		}
	}
	cout<<f[n+2]<<endl;
}

ARC184D Erase Balls 2D 题解

文章操作

相关推荐

评论

ARC184D Erase Balls 2D 题解