[BZOJ3167][P4099][HEOI2013]SAO(树形DP)
题目描述
Welcome to SAO ( Strange and Abnormal Online)。这是一个 VR MMORPG, 含有 n 个关卡。但是,挑战不同关卡的顺序是一个很大的问题。
有 n – 1 个对于挑战关卡的限制,诸如第 i 个关卡必须在第 j 个关卡前挑战, 或者完成了第 k 个关卡才能挑战第 l 个关卡。并且,如果不考虑限制的方向性, 那么在这 n – 1 个限制的情况下,任何两个关卡都存在某种程度的关联性。即, 我们不能把所有关卡分成两个非空且不相交的子集,使得这两个子集之间没有任 何限制。
输入输出格式
输入格式:
第一行,一个整数 T,表示数据组数。
对于每组数据,第一行一个整数 n,表示关卡数。接下来 n – 1 行,每行为 “i sign j”,其中 0 ≤ i, j ≤ n – 1 且 i ≠ j,sign 为“<”或者“>”,表示第 i 个关卡 必须在第 j 个关卡前/后完成。
输出格式:
对于每个数据,输出一行一个整数,为攻克关卡的顺序方案个数,mod 1,000,000,007 输出。
输入输出样例
说明
对于 20%的数据有 n ≤ 10。
对于 40%的数据有 n ≤ 100。
对于另外 20%的数据有,保证数据中 sign 只会是<,并且 i < j。
对于 100%的数据有 T ≤ 5,1 ≤ n ≤ 1000。
洛谷上都有的题BZ怎么还权限啊。。
这题在某种意义上和 [HNOI2015]实验比较 有相似之处,主要思路是通过树形DP和组合数求解。
直接给出状转方程:$f[i][j]$表示以$i$为根的子树中,$i$排在第$j$位的方案数。乘上组合数即可。
https://www.cnblogs.com/CQzhangyu/p/7605703.html、
最后前缀和优化那一步可能不太一样。但都是$O(n^3)$的,不知道是怎么过的,应该是因为根本跑不满。
#include<cstdio>
#include<cstring>
#include<algorithm>
#define mem(a) memset(a,0,sizeof(a))
#define rep(i,l,r) for (int i=l; i<=r; i++)
using namespace std; const int N=,mod=;
char c;
int n,T,u,v,cnt,C[N][N],g[N],f[N][N],to[N],sum[N][N],sz[N],h[N],nxt[N],val[N];
void add(int u,int v,int w){ to[++cnt]=v; val[cnt]=w; nxt[cnt]=h[u]; h[u]=cnt; }
void init(){ cnt=; mem(h); mem(f); mem(sum); mem(sz); } void dfs(int x,int fa){
f[x][]=sum[x][]=sz[x]=;
for (int i=h[x],s; i; i=nxt[i]) if ((s=to[i])!=fa){
dfs(s,x); mem(g);
if (val[i]==){
rep(i,,sz[x]) if (f[x][i]) rep(j,,sz[s]) if (sum[s][j])
g[i+j]=(g[i+j]+1ll*f[x][i]*sum[s][j]%mod*C[i+j-][i-]%mod*C[sz[x]-i+sz[s]-j][sz[x]-i]%mod)%mod;
}else{
rep(i,,sz[x]) if (f[x][i]) rep(j,,sz[s])
g[i+j]=(g[i+j]+1ll*f[x][i]*(sum[s][sz[s]]-sum[s][j]+mod)%mod*C[i+j-][i-]%mod*C[sz[x]-i+sz[s]-j][sz[x]-i])%mod;
}
sz[x]+=sz[s];
rep(i,,sz[x]) f[x][i]=g[i],sum[x][i]=(sum[x][i-]+g[i])%mod;
}
} int main(){
freopen("bzoj3167.in","r",stdin);
freopen("bzoj3167.out","w",stdout);
rep(i,,) C[i][]=;
rep(i,,) rep(j,,) C[i][j]=(C[i-][j-]+C[i-][j])%mod;
for (scanf("%d",&T); T--; ){
init(); scanf("%d",&n);
rep(i,,n){
scanf("%d %c%d",&u,&c,&v); u++; v++;
if (c=='>') swap(u,v);
add(u,v,); add(v,u,);
}
dfs(,); printf("%d\n",sum[][sz[]]);
}
return ;
}
最新文章
- Delphi_07_Delphi_Object_Pascal_基本语法_05_函数参数
- POJ 2923 状压好题
- HDU 5384 AC自动机
- 将golang程序注册为windows服务
- What is GSLB
- Python读取中文txt文件错误:UnicodeEncodeError: &#39;gbk&#39; codec can&#39;t encode character
- windows 32位系统中进程最大可用内存空间为3GB (转)
- [转]GCC参数详解
- iOS开发--使用NSMutableAttributedString 实现富文本
- Borg Maze
- 数字运算、ASCII
- VirtualBox更改虚拟机磁盘VDI的大小
- Linux 每日命令行
- 在IIS上部署(托管).NET Core站点
- ScheduledThreadPoolExecutor Usage
- LabVIEW(九):程序结构中的分支结构和顺序结构
- Centos7.2 Install subversion server
- Android Studio开发环境搭建和HelloWorld
- windows Server 2008 R2 TFS2010的备份
- curl 命令简介