[HNOI2015]实验比较

Description:

给你一些\(x < y\) ,\(x=y\) 的信息,求可能的原序列不同关系数
(每个\(x\)最多有一个\(x 的信息)

Hint:

$ n \le 100 $

Solution:

知道是树型dp,但还是不会

注意到等于的信息用并查集直接算作一个点就行,现在就是考虑这个<的条件

显然会形成一棵树,怎么算不同方案呢?

我们设\(f[i][j]\) 表示i的子树的序列用"<"分成了j段的方案数

这样dp可以很方便的合并子树信息:

考虑现在合并f[v1][x],f[v2][y],则第一段显然为i本身

剩下的j-1段由v1选x段,由于非空,再剩下的都选v2,v2多出来的再选

所以:

\[f[i][j]=f[v1][x]*f[v2][y]*C_{j-1}^{x-1}*C_{x-1}^{y-i+x} \]

(为什么是x-1,因为背包包含了i)

就是个树型背包

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define ls p<<1 
#define rs p<<1|1
using namespace std;
typedef long long ll;
const int mxn=1e2+5,mod=1e9+7;
int n,m,cnt,ans,vis[mxn],id[mxn],eq[mxn],in[mxn],hd[mxn+10];
int c[mxn+5][mxn+5],g[mxn],f[mxn][mxn],sz[mxn],fa[mxn];
int x[mxn],y[mxn];

inline int read() {
    char c=getchar(); int x=0,f=1;
    while(c>'9'||c<'0') {if(c=='-') f=-1;c=getchar();}
    while(c<='9'&&c>='0') {x=(x<<3)+(x<<1)+(c&15);c=getchar();}
    return x*f;
}
inline void chkmax(int &x,int y) {if(xy) x=y;}

struct ed {
    int to,nxt;
}t[mxn<<1];

inline void add(int u,int v) {
    t[++cnt]=(ed) {v,hd[u]}; hd[u]=cnt;
}

int find(int x) {
    return fa[x]==x?x:fa[x]=find(fa[x]);
}

void dfs(int u,int fa) {
    sz[u]=f[u][1]=1;
    for(int e=hd[u];e;e=t[e].nxt) {
        int v=t[e].to; if(v==fa) continue ; dfs(v,u);
        for(int i=1;i<=n;++i) g[i]=0;
        for(int i=1;i<=sz[u]+sz[v];++i) 
            for(int j=1;j<=sz[u];++j)
                for(int k=1;k<=sz[v];++k) {
                    int x=k-i+j; if(x<0) continue ;
                    g[i]=(g[i]+1ll*f[u][j]*f[v][k]%mod*c[i-1][j-1]%mod*c[j-1][x]%mod)%mod;
                }
        for(int i=1;i<=sz[u]+sz[v];++i) f[u][i]=g[i];		
        sz[u]+=sz[v];
    }
}

int main()
{
    n=read(); m=read(); 
    for(int i=0;i<=mxn;++i) c[i][0]=c[i][i]=1;
    for(int i=1;i<=mxn;++i) 
        for(int j=1;j
动态规划

相关

动态规划-------最短路径问题

背包问题c++动态规划方式

动态规划之矩阵连乘

动态规划 BZOJ1801 [Ahoi2009]chess 中国象棋

线性规划和动态规划

【学习笔记】动态规划—矩阵递推加速

[LeetCode]1320. Minimum Distance to Type a Word Using Two Fingers 动态规划解法

123. 买卖股票的最佳时机 III——动态规划-股票收益问题

最佳观光组合——动态规划

【51Nod】1510 最小化序列 贪心+动态规划

【BZOJ】3456: 城市规划 动态规划+多项式求逆

算法——动态规划(DP)

标签