正題

---

題目大意

一個$2?n$的矩形，求分歌成k塊的方案數。

---

解題思路

我們用$f_{i,j,0/1}$表示前i列，分成j塊，第i列是相同一塊還是分開的一塊。
然后我們分析

(不同顏色表示不同聯通塊)(字型體匯)

然后推出方程

(f[i][j][0]+=f[i-1][j-2][0])%=mod;(f[i][j][0]+=f[i-1][j-2][1])%=mod;(f[i][j][0]+=f[i-1][j-1][0]*2)%=mod;(f[i][j][0]+=f[i-1][j-1][1]*2)%=mod;(f[i][j][0]+=f[i-1][j][0])%=mod;(f[i][j][1]+=f[i-1][j-1][0])%=mod;(f[i][j][1]+=f[i-1][j-1][1])%=mod;(f[i][j][1]+=f[i-1][j][0]*2)%=mod;(f[i][j][1]+=f[i-1][j][1])%=mod;

---

code

#include<cstdio> #include<algorithm> #define mod 100000007 #define ll long long using namespace std; ll n,k,f[2001][2001][2]; int main() {scanf("%lld%lld",&n,&k);f[1][2][0]=f[1][1][1]=1;for(ll i=2;i<=n;i++)for(ll j=1;j<=min((i<<1),k);j++){(f[i][j][0]+=f[i-1][j-2][0])%=mod;(f[i][j][0]+=f[i-1][j-2][1])%=mod;(f[i][j][0]+=f[i-1][j-1][0]*2)%=mod;(f[i][j][0]+=f[i-1][j-1][1]*2)%=mod;(f[i][j][0]+=f[i-1][j][0])%=mod;(f[i][j][1]+=f[i-1][j-1][0])%=mod;(f[i][j][1]+=f[i-1][j-1][1])%=mod;(f[i][j][1]+=f[i-1][j][0]*2)%=mod;(f[i][j][1]+=f[i-1][j][1])%=mod;}printf("%lld",(f[n][k][0]+f[n][k][1])%mod); } 創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的nssl1193-地主【dp】的全部內容，希望文章能夠幫你解決所遇到的問題。

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