题意：给你n1个人，n2匹马站成一排，最多k1个人连续站，最多k2匹马连续站，问你有多少种方法
解题思路:4维dp，i,j,s,k分别代表位置，已经站了多少人，前一个站的是人还是马，一共连续站了几位了。
解题代码：
1 // File Name: 118d.cpp 2 // Author: darkdream 3 // Created Time: 2014年07月25日 星期五 15时35分03秒 4 5 #include<vector> 6 #include<list> 7 #include<map> 8 #include<set> 9 #include<deque> 10 #include<stack> 11 #include<bitset> 12 #include<algorithm> 13 #include<functional> 14 #include<numeric> 15 #include<utility> 16 #include<sstream> 17 #include<iostream> 18 #include<iomanip> 19 #include<cstdio> 20 #include<cmath> 21 #include<cstdlib> 22 #include<cstring> 23 #include<ctime> 24 #define LL long long 25 const int M = 100000000; 26 using namespace std; 27 int dp[204][200][3][20]; 28 int main(){ 29 int n1,n2,k1,k2; 30 scanf("%d %d %d %d",&n1,&n2,&k1,&k2); 31 memset(dp,0,sizeof(dp)); 32 dp[1][1][0][1] = 1; 33 dp[1][0][1][1] = 1; 34 35 for(int i = 2;i <= n1+n2;i ++){ 36 for(int j = 0 ;j <= n1;j ++){ 37 for (int s = 0;s <= 1; s ++){ 38 if((s && j == n1+1) ||(!s && i-j == n2+1)) 39 continue; 40 for(int k = 1;k <= (s?k2:k1);k ++){ 41 if(k == 1){ 42 for(int t = 1;t <= 10 ; t++) 43 { 44 dp[i][j][s][1] = (dp[i][j][s][1] + dp[i-1][(s?j:j-1)][!s][t] )%M; 45 } 46 }else{ 47 dp[i][j][s][k] = dp[i-1][(s?j:j-1)][s][k-1]; 48 } 49 // printf("%d %d %d %d %d ",i,j,s,k,dp[i][j][s][k]); 50 } 51 } 52 } 53 } 54 LL sum = 0 ; 55 56 for(int s = 0;s <= 1;s ++) 57 { 58 for(int i = 1;i <= 10 ;i ++) 59 { 60 sum = (sum +dp[n1+n2][n1][s][i])%M; 61 } 62 } 63 printf("%I64d ",sum); 64 return 0; 65 }