1 Codeforces 118D Caesar's Legions
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <algorithm> 6 #include <queue> 7 #include <vector> 8 #include <stack> 9 #include <map> 10 #include <set> 11 #include <cmath> 12 #include <cctype> 13 #include <ctime> 14 15 using namespace std; 16 17 #define REP(i, n) for (int i = 0; i < (n); ++i) 18 #define eps 1e-9 19 #define SZ(x) ((int)x.size()) 20 21 typedef long long ll; 22 typedef pair<int, int> pii; 23 const int mod = 1e8; 24 int n1, n2, k1, k2; 25 int dp[105][105][15][15]; 26 27 int main() { 28 #ifdef __AiR_H 29 freopen("in.txt", "r", stdin); 30 // freopen("out.txt", "w", stdout); 31 #endif // __AiR_H 32 scanf("%d %d %d %d", &n1, &n2, &k1, &k2); int ans = 0; 33 for (int i = 1; i <= min(n1, k1); ++i) { dp[i][0][i][0] = 1; } 34 for (int i = 1; i <= min(n2, k2); ++i) { dp[0][i][0][i] = 1; } 35 for (int i = 1 ; i <= n1; ++i) { 36 for (int j = 1; j <= n2; ++j) { 37 for (int k = 1; k <= min(j, k2); ++k) { 38 dp[i][j][1][0] += dp[i - 1][j][0][k]; 39 dp[i][j][1][0] %= mod; 40 } 41 for (int k = 1; k <= min(i, k1); ++k) { 42 dp[i][j][0][1] += dp[i][j - 1][k][0]; 43 dp[i][j][0][1] %= mod; 44 } 45 for (int k = 2; k <= min(k1, i); ++k) { 46 dp[i][j][k][0] += dp[i - 1][j][k - 1][0]; 47 dp[i][j][k][0] %= mod; 48 } 49 for (int k = 2; k <= min(k2, j); ++k) { 50 dp[i][j][0][k] += dp[i][j - 1][0][k - 1]; 51 dp[i][j][0][k] %= mod; 52 } 53 } 54 } 55 for (int i = 1; i <= min(n1, k1); ++i) { 56 ans += dp[n1][n2][i][0]; ans %= mod; 57 } 58 for (int i = 1; i <= min(n2, k2); ++i) { 59 ans += dp[n1][n2][0][i]; ans %= mod; 60 } 61 printf("%d ", ans); 62 #ifdef __AiR_H 63 printf("Time used = %.2fs ", (double)clock() / CLOCKS_PER_SEC); 64 #endif // __AiR_H 65 return 0; 66 }