?
# | Author | Problem | Lang | Verdict | Time | Memory | Sent | Judged | |
---|---|---|---|---|---|---|---|---|---|
12917082 |
Practice: zyf940104357 |
567F - 15 | GNU C++ | Accepted | 31 ms | 51656 KB | 2015-09-10 05:33:22 | 2015-09-10 05:33:23 |
#include<bits/stdc++.h> using namespace std; typedef long long int64; const int maxn=2015,maxk=100010; bool t[maxn][maxn]; int s[maxn][maxn]; int n,k; inline int get(int x1,int y1,int x2,int y2){ return s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]; } void init(){ memset(t,false,sizeof(t)); memset(s,0,sizeof(s)); for(int i=1;i<=k;++i){ int u,v; char str[5]; scanf("%d%s%d",&u,str,&v); if(str[0]=='>') swap(u,v),str[0]='<'; ++s[u][v]; if(str[0]=='=') ++s[v][u]; else if(!str[1]) t[u][v]=true; } for(int i=1;i<=(n<<1);++i) for(int j=1;j<=(n<<1);++j) s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1]; } int64 f[maxn][maxn]; void dp(){ memset(f,0,sizeof(f)); for(int i=1;i<=(n<<1)-1;++i) f[n][i]=!t[i][i+1] && !t[i+1][i]; for(int i=n-1;i>=1;--i){ for(int l=1,r=(n-i+1)<<1;r<=(n<<1);++l,++r){ if(!t[l][r] && !t[r][l] && !get(l+1,l,r-1,l) && !get(l+1,r,r-1,r)) f[i][l]+=f[i+1][l+1]; if(!t[l][l+1] && !t[l+1][l] && !get(l+2,l,r,l+1)) f[i][l]+=f[i+1][l+2]; if(!t[r-1][r] && !t[r][r-1] && !get(l,r-1,r-2,r)) f[i][l]+=f[i+1][l]; } } cout<<f[1][1]<<endl; } int main(){ while(scanf("%d%d",&n,&k)!=EOF) init(),dp(); return 0; }
?
?
?
?