Divide Chocolate（dp 2*n分成k个块）

原题： http://acm.hdu.edu.cn/showproblem.php?pid=4301

题意：

求2*n拆成k个块的方案数

解析：

从左往右遍历，最后一列只有两种状态：上下合在一起和上下分离。

设$dp[i][j][0]$为前i列分成j块，最后一列合在一起的方案数，$dp[i][j][1]$则为分离的方案数。

转移就是枚举右边三条小边的情况即可，有些是不合法的。

合并对后转移： 分离对后转移：

#include<bits/stdc++.h> using namespace std; #define LL long long #define rep(i,a,b) for(int i=a;i<=b;i++) LL read(){ LL ans=0; char last=' ',ch=getchar(); while(ch<'0' || ch>'9')last=ch,ch=getchar(); while(ch>='0' && ch<='9')ans=ans*10+ch-'0',ch=getchar(); if(last=='-')ans=-ans; return ans; } const LL mod=100000007 ; const int maxn=1009; LL dp[maxn][maxn<<1][2]; inline void add(LL &a,LL b){ a=(a+b)%mod; } int main(){ int size = 512 << 20; // 512MB char *p = (char*)malloc(size) + size; __asm__("movl %0, %%esp\n" :: "r"(p)); int t;scanf("%d",&t); dp[1][1][0]=1; dp[1][2][1]=1; rep(i,1,999){ rep(j,1,2*i){ add(dp[i+1][j][0],dp[i][j][0]); add(dp[i+1][j+2][1],dp[i][j][0]); add(dp[i+1][j+1][1],dp[i][j][0]); add(dp[i+1][j+1][1],dp[i][j][0]); add(dp[i+1][j+1][0],dp[i][j][0]); add(dp[i+1][j][1],dp[i][j][1]); add(dp[i+1][j+1][1],dp[i][j][1]); add(dp[i+1][j+1][1],dp[i][j][1]); add(dp[i+1][j][0],dp[i][j][1]); add(dp[i+1][j][0],dp[i][j][1]); add(dp[i+1][j+1][0],dp[i][j][1]); add(dp[i+1][j+2][1],dp[i][j][1]); } } while(t--){ int n,k;scanf("%d%d",&n,&k); printf("%lld\n",(dp[n][k][0]+dp[n][k][1])%mod); } }