题意
在平面直角坐标系上有(n)个点，没有重合的点。你要从这(n)个点向上下左右四个方向的其中一个引一条射线，最终没有射线相交，求方案数。
(nleq 54)
Solution
有dick意思的dp。
暴力是(O(4^n))，太水就不说了。
正解：
先把(n)个点按照(y)坐标从大到小排序，离散化横坐标。
设(f_{i,j,k,l,m})表示已经确定了前(i)个点的方向，其中向右的点中最小横坐标的是(j)，向左的点中最大的横坐标是(k)，向下的点中最小的横坐标是(l)，向下的点中最大的横坐标是(m)，这种情况下的方案数。
初始状态(f[0][max+1][0][max+1][0]=1)，其他都是(0)。（max是离散化后横坐标最大值+1）
首先还要预处理一个(ok[i][0..3])（英语不好只能用ok了），表示(i)选这四个方向会不会直接与某个点相交。
那么转移时就只需要枚举(i+1)的方向，用(ok)判掉不合法的，再用已知的(j,k,l,m)判掉不合法的就行了。
最终答案就是(sum f_{n,j,k,l,m})
由于状态占用空间较大，我们需要把第一维(i)用滚动数组优化掉，这样空间复杂度就是(O(n^4))。
时间复杂度理论上是(O(n^5))，实际上达不到这个上界，因为有大量冗余状态，转移时可以排除掉，问题就解决了。
Code
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 56, P = 998244353;
int n, len, arr[N], ok[N][4], f[2][N][N][N][N];
struct point { int x, y; } p[N];
int cmp(point a, point b) { return a.y == b.y ? a.x < b.x : a.y > b.y; }
void plus(int &a, int b) { a = (a + b) % P; }
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d%d", &p[i].x, &p[i].y);
sort(p + 1, p + n + 1, cmp);
for (int i = 1; i <= n; i++) arr[++len] = p[i].x;
sort(arr + 1, arr + len + 1);
len = unique(arr + 1, arr + len + 1) - arr - 1;
for (int i = 1; i <= n; i++) p[i].x = lower_bound(arr + 1, arr + len + 1, p[i].x) - arr;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j < i; j++)
{
if (p[i].x == p[j].x) ok[i][0] = 1;
if (p[i].y == p[j].y)
{
if (p[i].x > p[j].x) ok[i][1] = 1;
if (p[i].x < p[j].x) ok[i][3] = 1;
}
}
for (int j = i + 1; j <= n; j++)
{
if (p[i].x == p[j].x) ok[i][2] = 1;
if (p[i].y == p[j].y)
{
if (p[i].x > p[j].x) ok[i][1] = 1;
if (p[i].x < p[j].x) ok[i][3] = 1;
}
}
}
f[0][0][len + 1][0][len + 1] = 1;
for (int i = 0, now = 0, nx; i < n; i++)
{
nx = now ^ 1;
memset(f[nx], 0, sizeof(f[nx]));
for (int j = 0; j <= len + 1; j++)
for (int k = 0; k <= len + 1; k++)
for (int l = 0; l <= len + 1; l++)
for (int m = 0; m <= len + 1; m++)
if (f[now][j][k][l][m])
{
if (!ok[i + 1][0] && j < p[i + 1].x && k > p[i + 1].x) plus(f[nx][j][k][l][m], f[now][j][k][l][m]);
if (!ok[i + 1][1] && m > p[i + 1].x) plus(f[nx][max(j, p[i + 1].x)][k][l][m], f[now][j][k][l][m]);
if (!ok[i + 1][2]) plus(f[nx][j][k][max(l, p[i + 1].x)][min(m, p[i + 1].x)], f[now][j][k][l][m]);
if (!ok[i + 1][3] && l < p[i + 1].x) plus(f[nx][j][min(k, p[i + 1].x)][l][m], f[now][j][k][l][m]);
}
now ^= 1;
}
int ans = 0;
for (int j = 0; j <= len + 1; j++)
for (int k = 0; k <= len + 1; k++)
for (int l = 0; l <= len + 1; l++)
for (int m = 0; m <= len + 1; m++)
plus(ans, f[n & 1][j][k][l][m]);
printf("%d
", ans);
return 0;
}