其實說實在 我在寫這篇博客的時候 才剛剛草了一道這樣類型的題 之前幾乎沒有接觸過 接觸過也是平時比賽的 沒有系統的做過 可以說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\n",(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:\n",Tcase);int ans=0; printf("%lld\n",F[K][(1<<N)-1]);}return 0; } View Code

?

轉載于:https://www.cnblogs.com/wohenshuai/p/5901620.html

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的[DP之计数DP]的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。