首页 > 代码库 > codeforces118D - Caesar's Legions 多维DP

codeforces118D - Caesar's Legions 多维DP

2024-07-14 01:00:30   218人阅读

题意：给你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\n",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\n",sum);64 return 0;65 }
View Code


联系
我们