[DP之计数DP]

其实说实在我在写这篇博客的时候才刚刚草了一道这样类型的题之前几乎没有接触过接触过也是平时比赛的没有系统的做过可以说0基础

我所理解的计数dp就是想办法去达到它要的目的而且一定要非常劲非常快都是一个很小的数然后有很多种接下来的方案使得这个数一下子变很大

计数DP常用的有：组合和排列然后要抽象的想还有容斥定理(这的话经常考而且很难几乎不会做) 还有用前缀之类的进行优化转移找到规律就可以搞了

慢慢给出例题慢慢说慢慢学因为这个要不全AC要不全WA

[JLOI2013]地形生成

计数dp的第一题看了题意一下子懵比感受到了计数dp的厉害性表示连暴力都不会打

然后看题解自己推了做了死吭了一天 (妈的旁边合唱室的脑瓜有病啊我去叫了一整天还不给我唱征服..)

首先我们发现如果小的插在大的前面是完全没有影响的所以我们按两个关键字从大到小排这样的话以后插入都没有影响

看上去好像第一问简单一点就是求合法的标号序列也就是合法的序列有多少个那么想一想嘛对于同一个高度的你找到前面的你能插到哪里再加上高度相同的而且在前面的

为什么要加上前面的呢你想想前面是不是也是找前面的那么他们找了的话其实我当前的可以把这个位置忽略掉并且前面的还会把它找的前面给挤出去然后还多了个位置

比如说 x y 都在我承受的范围内就有三个可以放的地方但是加上了前面高度相同的还有一个p 也就是变成了 x p y 那么是不是多了个位置啊就有四个地方可以插入了

然后就是高度序列的问题高度序列其实想一想就是同一个高度的然后两两的位置不能变这也和我们两个关键字排序有关小的在前大的在后这样的话保证高度相同时后面的可以放在前面去

不能交换的话那么怎么做呢其实也很简单想想就好

设F[i][j]表示现在是第i座山放在第j个位置上占时对于这个高度有多少种方法

那么这个高度第一座山所有这座山能放位置的F[i][j]=1

考虑下一座山不能放在上一座山的前面不然就相当于这一座山是第一座上一座是第二座就交换了

所以的话F[i+1][j]=sigma(F[i][1..j-1]) 就是上一座山放在我前面的都可以继承下来然后的话搞一个前缀和优化一下

F[i+1][j]=F[i+1][j-1]+F[i][j-1] 也就是说前面能选的我也可以选前面不可以选的我可以选就是前面那座山在前面的位置

然后每个最后的山的状态的和加起来就好了这就代表了这个高度的山一起放的方案数然后乘一下就好

代码贼短不用怕

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#define Maxn 1010
using namespace std;
const int Mod=2011;
pair<int,int>pr[Maxn];
bool Cmp(const pair<int,int> &x,const pair<int,int> &y){if(x.first!=y.first) return x.first>y.first; else return x.second<y.second;}
int F[Maxn][Maxn];
int main()
{
  int N; scanf("%d",&N);
  for(int i=1;i<=N;i++) scanf("%d%d",&pr[i].first,&pr[i].second);
  sort(pr+1,pr+N+1,Cmp); int ans1=1,ans2=1; memset(F,0,sizeof(F));
   
  for(int i=1;i<=N;)
  {
    int now=i; while(now<N&&pr[now].first==pr[now+1].first) now++;
    for(int j=i;j<=now;j++)
    {
      ans1=(ans1*(min(pr[j].second,i)+j-i))%Mod;
       
      if(j==i){F[j][0]=1; for(int k=1;k<min(pr[j].second,i)+j-i;k++) F[j][k]=(F[j][k-1]+F[j][k])%Mod;}
      else for(int k=0;k<min(pr[j].second,i)+j-i;k++) F[j][k]=(F[j][k-1]+F[j-1][k-1])%Mod;
    }
    int sum=0; for(int j=0;j<min(pr[now].second,i)+now-i;j++) sum+=F[now][j];
    ans2=(ans2*sum)%Mod; i=now+1;
  }
  return printf("%d %d",ans1,ans2),0;
}
/*
2
1 2
2 2
*/

View Code

Codeforce 382.E Ksenia and Combinatorics

好难啊啊啊好想死啊做了我一天半

题目有一个最大匹配数有一个不同子树形态数学老师其实教过我们做题要有化归思想

单单求子树形态我们可以有两种方法：

1.强制左树小于右树且左树和右树相同时最小的数在左树

2.强制左树小于右树且相同时 /2

单单求最大匹配数我们可以有 F[i][0/1]表示与不与根匹配转移显然

然后要合起来怎么办呢定义F[N][K][0/1]表示N个点最大匹配数为k然后最上面的点选不选

然后我们固定一个根

复制一下别人的图其实C(k,i-1)就是选一边的根节点固定不能变然后因为上一个状态继承下一个状态的时候下一个状态的根节点是可以变得所以要两边分别乘k和(i-k-1)

然后没了好多细节有点难打注意相同节点个数的时候要除2(画图大概意会了一下想了好久不会证，大概是所有形态只是选的方式不同形态是一样的) k=0是要*1

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdlib>
using namespace std;
typedef long long LL;
const LL Mod=1e9+7;
LL N,K; LL C[60][60]; LL F[60][60][2];
void Pre()
{
  C[1][1]=1; for(LL i=1;i<=N;i++) C[i][0]=1;
  for(LL i=2;i<=N;i++) for(LL j=1;j<=i;j++) C[i][j]=(C[i-1][j-1]+C[i-1][j]);
}
int main()
{
  scanf("%I64d%I64d",&N,&K); Pre();
  F[0][0][1]=1; F[1][0][0]=1;
  for(LL p=2;p<=N;p++)
  {
    for(LL q=0;q<=p/2;q++)
    {
      for(LL i=0;i<=(p-1)/2;i++)
      {
        for(LL j=0;j<=i/2;j++)
        {
          LL k0=1,k1=1; if(i==p-i-1) k0++; if(i==p-i-1) k1++;
          LL A=i; LL B=p-i-1; if(A==0) A++;
          
          LL cz=((C[p-1][i]/k0)*A*B)%Mod;
          cz=(cz*F[i][j][1])%Mod; cz=(cz*F[p-i-1][q-j][1])%Mod;
          F[p][q][0]=(F[p][q][0]+cz)%Mod;
          
          cz=((C[p-1][i]/k1)*A*B)%Mod;
          cz=(cz*((F[i][j][1]*F[p-i-1][q-j-1][0])%Mod+(F[i][j][0]*F[p-i-1][q-j-1][1])%Mod+(F[i][j][0]*F[p-i-1][q-j-1][0])%Mod))%Mod;
          F[p][q][1]=(F[p][q][1]+cz)%Mod;
        }
      }
    }
  }
  printf("%I64d
",(F[N][K][0]+F[N][K][1])%Mod);
  return 0;
}

View Code

hdu5713 K个联通块

绝世好题啊(不是bzoj4300..)

首先N这么小就应该想到什么组合容斥状压然后又有一个K 很明显这是要转移的

F[sta][K]表示点的状态为sta 分成K份的方案数那么我们考虑转移先在状态中抽出一个点然后和其余的点互相成为联通块

比如说这个状态有4个点 1 2 3 4 我把1抽出来使得1 12 13 14 123 124 134成为联通块设为上一个状态s1 然后求解 F[sta][K]=Sigma(F[s1][1],F[sta^s1][k-1])

这样就没有遗漏的这是liao教我的因为这样保证了你1这个联通块是不同的然后其他的块随便取这样就保证结果都是不同的而且1是一定要取得，全部都会取完

也就是1总得要属于一个联通块然后你把联通块枚举出来其它一定不同而且一定要算了

但是我们需要做的是F[sta][1] 其实的话这个状态就可以转换成G[sta]-H[sta] G是这个状态所有的边的方案数通过2^(边数)可以求出然后H就是这个状态不联通的个数

H的求法类似于F H[sta]=H[s1]*G[sta^s1] 就是随便抽一个点出来然后其它怎么连都不关我事这样就每个和这个点的联通块都过了一变保证不重复

求子集有点妙自己看看代码意会

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#define Maxn 15
using namespace std;
typedef long long LL;
const int Mod=1e9+9;
struct node{int x,y,next;}edge[Maxn*Maxn*2]; int len,first[Maxn];
void ins(int x,int y){len++; edge[len].x=x; edge[len].y=y; edge[len].next=first[x]; first[x]=len;}
int T,K,N,M; inline int low_bit(int x){return x&(-x);}

LL G[1<<Maxn]; LL F[Maxn][1<<Maxn]; LL H[1<<Maxn];
LL bit[Maxn*Maxn];
int main()
{
  scanf("%d",&T);
  for(int Tcase=1;Tcase<=T;Tcase++)
  {
    scanf("%d%d%d",&N,&M,&K); len=0; memset(first,-1,sizeof(first));
    for(int i=1;i<=M;i++){int a,b; scanf("%d%d",&a,&b); if(a>=b) ins(a,b); else ins(b,a);}
    bit[0]=1; for(int i=1;i<=M;i++) bit[i]=(bit[i-1]<<1)%Mod;
    memset(F,0,sizeof(F)); memset(G,0,sizeof(G)); memset(H,0,sizeof(H));
    
    for(int i=0;i<(1<<N);i++)
    {
      int sum=0;
      for(int x=1;x<=N;x++)
        for(int k=first[x];k!=-1;k=edge[k].next)
        {
          int y=edge[k].y;
          if((i&(1<<(x-1)))&&(i&(1<<(y-1))))
            sum++;
        }
      G[i]=bit[sum];
    }
    
    for(int i=0;i<(1<<N);i++)
    {
      int last=i-low_bit(i);
      for(int j=last;j;j=(j-1)&last)
        H[i]=(H[i]+(F[1][i-j]*G[j]))%Mod;
      F[1][i]=(G[i]-H[i]+Mod)%Mod;
    }
    
    for(int k=2;k<=K;k++)
      for(int i=0;i<(1<<N);i++)
      {
        int last=i-low_bit(i);
        for(int j=last;j;j=(j-1)&last)
          F[k][i]=(F[k][i]+(F[1][i-j]*F[k-1][j]))%Mod;
      }
    
    printf("Case #%d:
",Tcase);
    int ans=0; printf("%lld
",F[K][(1<<N)-1]);
  }
  return 0;
}

View Code