用java做网站的步骤/网站建设网站

$Description$

给定$n$个点及它们的坐标，满足它们的坐标都是整数，若它们可以射出与坐标轴平行的射线，求它们射线没有一个射线相交的方案数（必须射出）

对于前30%的数据，$n\le 9$。
对于前40%的数据，$n\le 18$。
对于前60%的数据，$n\le 36$。
对于前100%的数据，$n\le 54$，对于所有$i,j$，有$x_i̸=x_j$或$y_i̸=y_j$，且$|x_i|,|y_i|\le {10}^9$。

$Solution$

$dp$

首先将坐标按$x$排序，然后接下来$dp$转移即可

$Code$

#include<cstdio>
#include<cctype>
#include<algorithm>
#define wyc 998244353
#define rs(a,b,c,d,e) for(a=0;a<e;a++)for(b=0;b<e;b++)for(c=0;c<e;c++)for(d=0;d<e;d++)
using namespace std;
struct node{int x,y;}p[55];
inline bool cmp(node x,node y){return x.x<y.x||x.x==y.x&&x.y<y.y;}//按横坐标排序 
bool ok[55][4];
int n,f[2][55][55][55][55],now,nxt,anxt,bnxt,cnxt,dnxt,a,b,c,d;
long long ans;
inline char Getchar()
{static char buf[10000000],*p1=buf+10000000,*pend=buf+10000000;if(p1==pend){p1=buf; pend=buf+fread(buf,1,10000000,stdin);if (pend==p1) return -1;}return *p1++;
}
inline long long read()
{char c;int d=1;long long f=0;while(c=Getchar(),!isdigit(c))if(c==45)d=-1;f=(f<<3)+(f<<1)+c-48;while(c=Getchar(),isdigit(c)) f=(f<<3)+(f<<1)+c-48;return d*f;
}
signed main()
{n=read();for(register int i=1;i<=n;i++) p[i]=(node){read(),read()};sort(p+1,p+1+n,cmp);for(register int i=1;i<=n;i++){ok[i][0]=ok[i][1]=ok[i][2]=ok[i][3]=true;for(register int j=1;j<=n;j++)if(i!=j){if(p[i].y==p[j].y&&p[i].x>p[j].x) ok[i][0]=false;//纵坐标相等，横坐标更大，则不能向左 if(p[i].x==p[j].x&&p[i].y<p[j].y) ok[i][1]=false;//横坐标相同，纵坐标更小，则不能向上if(p[i].y==p[j].y&&p[i].x<p[j].x) ok[i][2]=false;//纵坐标相等，横坐标更小，则不能向右if(p[i].x==p[j].x&&p[i].y>p[j].y) ok[i][3]=false;//横坐标相同，纵坐标更大，则不能向下 if(!ok[i][0]&&!ok[i][1]&&!ok[i][2]&&!ok[i][3]) break;}}f[0][0][0][0][0]=1;nxt=1;for(register int i=1;i<=n;now^=1,nxt^=1,i++){rs(a,b,c,d,i)if(f[now][a][b][c][d]){if(ok[i][0])//若能向左{if((!c||p[c].y>p[i].y)&&(!d||p[d].y<p[i].y)){anxt=a;bnxt=b;cnxt=c;dnxt=d;(f[nxt][anxt][bnxt][cnxt][dnxt]+=f[now][a][b][c][d])%=wyc;}}if(ok[i][1])//若能向上 {if(!b||p[i].y>p[b].y){anxt=a;bnxt=b;cnxt=c;dnxt=d;if(!c||p[i].y<p[c].y) cnxt=i; (f[nxt][anxt][bnxt][cnxt][dnxt]+=f[now][a][b][c][d])%=wyc;}}if(ok[i][2])//若能向右 {anxt=a;bnxt=b;cnxt=c;dnxt=d;if(!a||p[i].y<p[a].y) anxt=i;if(!b||p[i].y>p[b].y) bnxt=i;(f[nxt][anxt][bnxt][cnxt][dnxt]+=f[now][a][b][c][d])%=wyc;}if(ok[i][3])//若能向下 {if(a==0||p[i].y<p[a].y){anxt=a;bnxt=b;cnxt=c;dnxt=d;if(!d||p[i].y>p[d].y) dnxt=i; (f[nxt][anxt][bnxt][cnxt][dnxt]+=f[now][a][b][c][d])%=wyc;}}}rs(a,b,c,d,i+1) f[now][a][b][c][d]=0;}now=n&1;rs(a,b,c,d,n+1) ans+=f[now][a][b][c][d];printf("%lld",ans%wyc);
}