This way
给你一个长度为n，宽度为2的巧克力，问你将它分成k份有多少种方法，每个单位的巧克力是不一样的。
想到DP之后就很好做了，首先对于第i位，这两个块可以并在一起，可以分开，所以DP需要开三维 d p [ 0 / 1 ] [ i ] [ j ] dp[0/1][i][j] dp[0/1][i][j]表示到第i位的时候分成了j份，最后一格是并起来或者分开的情况数。我用 [ 0 ] [0] [0]表示并， [ 1 ] [1] [1]表示分开。那么状态转移方程就是 d p [ 0 ] [ i ] [ j ] = ( d p [ 0 ] [ i − 1 ] [ j ] + d p [ 0 ] [ i − 1 ] [ j − 1 ] + d p [ 1 ] [ i − 1 ] [ j − 1 ] + d p [ 1 ] [ i − 1 ] [ j ] ∗ 2 ) % m o d dp[0][i][j]=(dp[0][i-1][j]+dp[0][i-1][j-1]+dp[1][i-1][j-1]+dp[1][i-1][j]*2)\%mod dp[0][i][j]=(dp[0][i−1][j]+dp[0][i−1][j−1]+dp[1][i−1][j−1]+dp[1][i−1][j]∗2)%mod d p [ 1 ] [ i ] [ j ] = ( d p [ 1 ] [ i − 1 ] [ j ] + d p [ 0 ] [ i − 1 ] [ j − 1 ] ∗ 2 + d p [ 1 ] [ i − 1 ] [ j − 1 ] ∗ 2 + ( j > = 2 ? d p [ 1 ] [ i − 1 ] [ j − 2 ] + d p [ 0 ] [ i − 1 ] [ j − 2 ] : 0 ) ) % m o d dp[1][i][j]=(dp[1][i-1][j]+dp[0][i-1][j-1]*2+dp[1][i-1][j-1]*2+(j>=2?dp[1][i-1][j-2]+dp[0][i-1][j-2]:0))\%mod dp[1][i][j]=(dp[1][i−1][j]+dp[0][i−1][j−1]∗2+dp[1][i−1][j−1]∗2+(j>=2?dp[1][i−1][j−2]+dp[0][i−1][j−2]:0))%mod 这个用稍微想一想就能知道为什么了。
#include<bits/stdc++.h> using namespace std; #define ll long long const ll mod=100000007; const int N=1e3+5; ll dp[2][N][N*2]; int main() { int t; scanf("%d",&t); dp[0][1][1]=1,dp[0][1][2]=0; dp[1][1][1]=0,dp[1][1][2]=1; for(int i=2;i<=1000;i++) { for(int j=1;j<=2000;j++) { dp[0][i][j]=(dp[0][i-1][j]+dp[0][i-1][j-1]+dp[1][i-1][j-1]+dp[1][i-1][j]*2)%mod; dp[1][i][j]=(dp[1][i-1][j]+dp[0][i-1][j-1]*2+dp[1][i-1][j-1]*2+(j>=2?dp[1][i-1][j-2]+dp[0][i-1][j-2]:0))%mod; } } while(t--) { int n,k; scanf("%d%d",&n,&k); printf("%lld\n",(dp[0][n][k]+dp[1][n][k])%mod); } return 0; }