[清橙A1210]光棱坦克

题目大意：

平面上放置了\(n(n\le7000)\)个反射装置，光纤将从某个装置出发，在经过一处装置时发生反射，若经过的装置坐标依次为\((x_1,y_1),(x_2,y_2),\ldots,(x_k,t_k)\)，则必须满足：

• \(\forall j \in (1,k],y_j< y_{j-1}\)
• \(\forall j\in (2,k],x_{j-2}< x_j < x_{j-1} \vee x_{j-1}< x_j < x_{j-2}\)
  
  两种光线不同当且仅当经过的折射装置的集合不同，求总共有多少种合法的光线。

思路：

一个很显然的\(\mathcal O(n^3)\)的动态规划是，首先将所有点按照\(y\)排序，\(f_{i,j}\)表示考虑前\(i\)个装置，最后一个点是\(i\)，上一个点的\(x\)是\(j\)的方案数。前缀和优化到\(\mathcal O(n^2)\)，空间\(\mathcal O(n^2)\)。

然而这题要求空间复杂度是\(\mathcal O(n)\)。

于是就有了下面\(\mathcal O(n)\)空间的新做法。

源代码：

#include<cstdio>

#include<cctype>

#include<algorithm>

inline int getint() {

	register char ch;

	register bool neg=false;

	while(!isdigit(ch=getchar())) neg|=ch=='-';

	register int x=ch^'0';

	while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');

	return neg?-x:x;

}

const int N=7002;

struct Point {

	int x,y;

	bool operator < (const Point &rhs) const {

		return x>rhs.x;

	}

};

Point p[N];

int f[N][2];

int main() {

	const int n=getint(),mod=getint();

	for(register int i=1;i<=n;i++) {

		p[i].x=getint();

		p[i].y=getint();

	}

	std::sort(&p[1],&p[n]+1);

	for(register int i=1;i<=n;i++) {

		f[i][0]=f[i][1]=1;

		for(register int j=i-1;j;j--) {

			if(p[j].y<p[i].y) (f[i][0]+=f[j][1])%=mod;

			if(p[j].y>p[i].y) (f[j][1]+=f[i][0])%=mod;

		}

	}

	int ans=mod-n;

	for(register int i=1;i<=n;i++) {

		(ans+=f[i][0])%=mod;

		(ans+=f[i][1])%=mod;

	}

	printf("%d\n",ans);

	return 0;

}