hdu 5181 numbers——思路+区间DP

题目:http://acm.hdu.edu.cn/showproblem.php?pid=5181

题解:https://www.cnblogs.com/Miracevin/p/10960717.html

原来卡特兰数的这个问题还能区间DP……

XO

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
int rdn()
{
int ret=;bool fx=;char ch=getchar();
while(ch>''||ch<''){if(ch=='-')fx=;ch=getchar();}
while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();
return fx?ret:-ret;
}
const int N=,M=9e5+,mod=1e9+;
int n,m,hd[N],xnt,to[M],nxt[M],b[N][N],f[N][N];
bool vis[N];
void init()
{
memset(b,,sizeof b); memset(f,,sizeof f);
xnt=; memset(hd,,sizeof hd);
}
void add(int x,int y){to[++xnt]=y;nxt[xnt]=hd[x];hd[x]=xnt;}
void dfs(int cr)
{
for(int i=hd[cr],v;i;i=nxt[i])
if(!vis[v=to[i]])
{
vis[v]=; b[cr][v]=; dfs(v);
}
}
bool chk(int x1,int x2,int y1,int y2)
{
if(x2<x1||y2<y1)return true;
int tp=b[x2][y2]-b[x1-][y2]-b[x2][y1-]+b[x1-][y1-];
return !tp;
}
void solve()
{
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
b[i][j]+=b[i][j-];
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
b[i][j]+=b[i-][j];
for(int len=;len<=n;len++)
{
for(int i=;i<=n;i++)
{
int j=i+len-; if(j>n)break;
f[i][i-]=f[j+][j]=;
for(int k=i;k<=j;k++)
{
if(chk(k,j,i,k-)&&chk(k,k,k+,j))
f[i][j]=(f[i][j]+(ll)f[i][k-]*f[k+][j])%mod;
}
}
}
printf("%d\n",f[][n]);
}
int main()
{
int T=rdn();
while(T--)
{
init();
n=rdn();m=rdn();
for(int i=,u,v;i<=m;i++)
u=rdn(),v=rdn(),add(u,v);
for(int i=;i<=n;i++)
{
memset(vis,,sizeof vis);
dfs(i);
}
bool fg=;
for(int i=;i<=n&&(!fg);i++)
for(int j=;j<=i;j++)
if(b[i][j]&&b[j][i]){fg=;break;}
if(fg){puts("");continue;}
solve();
}
return ;
}
上一篇:linux下usb驱动接口中端点介绍


下一篇:HDU 4632 Palindrome subsequence(区间dp,回文串,字符处理)