题目:http://www.51nod.com/onlineJudge/questionCode.html
很好的思想。考虑从小到大一对一对填数,这样也能对它的大小限制做一些操作了。
因为从小到大,所以只能全填在左边、全填在右边、两边各填一个。记录左边填到了哪个位置,就可知右边填到了哪个位置。转移之前判断一下这样填是否合法即可。
新的不合法的状态只会和现在填的两个位置有关。
注意输入格式!!符号前后有空格!!!
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int N=,M=;
int n,m,x[M],y[M],sgn[M],tx,ty;
ll dp[N][N<<],ans;
char ch[];
bool check(int p0,int p1,int r,int fx)
{
//printf("p0=%d p1=%d r=%d fx=%d\n",p0,p1,r,fx);
for(int i=;i<=m;i++)
if(sgn[i]==&&
( ( (x[i]==p0||x[i]==p1)&&y[i]!=p0&&y[i]!=p1)||
( (y[i]==p0||y[i]==p1)&&x[i]!=p0&&x[i]!=p1) ) )
return ;//以前都合法,不合法仅出现在p0、p1位置上
if(!fx)
{
for(int i=;i<=m;i++)
{
//printf("sgn[%d]=%d\n",i,sgn[i]);
if(sgn[i]==||sgn[i]==)
{
tx=x[i];ty=y[i];
if(sgn[i]==)swap(tx,ty);
//printf("tx=%d ty=%d p0=%d p1=%d r=%d\n",tx,ty,p0,p1,r);
if((ty==p0||ty==p1)&&tx>=p0&&tx<r) return ;
}
if(sgn[i]==||sgn[i]==)
{
tx=x[i];ty=y[i];
if(sgn[i]==)swap(tx,ty);
if((ty==p0||ty==p1)&&tx>p1&&tx<r) return ;
}
}
}
if(fx==)
{
for(int i=;i<=m;i++)
{
if(sgn[i]==||sgn[i]==)
{
tx=x[i];ty=y[i];
if(sgn[i]==)swap(tx,ty);
if((ty==p0||ty==p1)&&tx<=p1&&tx>r) return ;
}
if(sgn[i]==||sgn[i]==)
{
tx=x[i];ty=y[i];
if(sgn[i]==)swap(tx,ty);
if((ty==p0||ty==p1)&&tx<p0&&tx>r) return ;
}
}
}
if(fx==)
{
for(int i=;i<=m;i++)
{
if(sgn[i]==||sgn[i]==)
{
tx=x[i];ty=y[i];
if(sgn[i]==)swap(tx,ty);
if((ty==p0||ty==p1)&&tx>=p0&&tx<=p1) return ;
}
if(sgn[i]==||sgn[i]==)
{
tx=x[i];ty=y[i];
if(sgn[i]==)swap(tx,ty);
if((ty==p0||ty==p1)&&tx>p0&&tx<p1) return ;
}
}
}
return ;
}
int main()
{
scanf("%d%d",&n,&m);ch[]=getchar();
while(ch[]!='\n')ch[]=getchar();
for(int i=,len=,j;i<=m;i++,len=)
{
ch[++len]=getchar();
while(ch[len]!='\n')ch[++len]=getchar();
for(j=;j<len;j++)
{
if(ch[j]>=''&&ch[j]<='')
x[i]=(x[i]<<)+(x[i]<<)+ch[j]-'';
else break;
}
while(ch[j]==' ')j++;
//printf("j=%d chj=(%c)\n",j,ch[j]);
if(ch[j]=='=') sgn[i]=,j++;
else if(ch[j]=='<'&&ch[j+]=='=')sgn[i]=,j+=;
else if(ch[j]=='>'&&ch[j+]=='=')sgn[i]=,j+=;
else if(ch[j]=='<')sgn[i]=,j++;
else if(ch[j]=='>')sgn[i]=,j++;
while(ch[j]==' ')j++;
//printf("j=%d chj=(%c)\n",j,ch[j]);
for(;j<len;j++)
y[i]=(y[i]<<)+(y[i]<<)+ch[j]-'';
//printf("x=%d sgn=%d y=%d\n",x[i],sgn[i],y[i]);
}
dp[][]=;
for(int i=,lm;i<n;i++)
{
lm=(i<<);
for(int j=,r;j<=lm;j++)
{
//if(dp[i][j])printf("dp[%d][%d]=%lld\n",i,j,dp[i][j]);
r=(n<<)-(lm-j)+;
if(check(j+,j+,r,))
dp[i+][j+]+=dp[i][j];
//printf("dp[%d][%d]=%lld(%d,%d)\n",i+1,j+2,dp[i+1][j+2],i,j);
if(check(r-,r-,j,))
dp[i+][j]+=dp[i][j];
//printf("dp[%d][%d]=%lld(%d,%d)\n",i+1,j,dp[i+1][j],i,j);
if(check(j+,r-,,))
dp[i+][j+]+=dp[i][j];
//printf("dp[%d][%d]=%lld(%d,%d)\n",i+1,j+1,dp[i+1][j+1],i,j);
}
}
int lm=(n<<);
for(int j=;j<=lm;j++) ans+=dp[n][j];
printf("%lld\n",ans/);
return ;
}