Решение задачи Легионы Цезаря с Codeforces

Без пояснения   Просмотров: 33


Знаменитый полководец Гай Юлий Цезарь любил выстраивать воинов своей армии в шеренгу. Всего в армии было n 1 пехотинцев и n 2 всадников. Цезарь считал, что расстановка не красивая, если где-то в строю стоит подряд строго больше k 1 пехотинцев или строго больше k 2 всадников. Найдите количество красивых расстановок воинов.

Учтите, что в каждой расстановке должны присутствовать все n 1 + n 2 воинов. Все пехотинцы считаются неразличимыми между собой. Аналогично, все всадники считаются неразличимыми между собой.

Код

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ul;
typedef long double ld;

ll k, l, m, n, sum, dp[105][105][12][12], mod(1e8);

ll z(ll a, ll b, ll c, ll d){
    if(a==0&&b==0){
        return 1;
    }
    else if(dp[a][b][c][d]==-1){
        ll sum=0;
        if(a>0&&c>0)(sum+=z(a-1,b,c-1,n))%mod;
        if(b>0&&d>0)(sum+=z(a,b-1,m,d-1))%mod;
        dp[a][b][c][d]=sum%mod;
    }
    return dp[a][b][c][d];
}

int main(){
    cin>>k>>l>>m>>n;
    memset(dp,-1,sizeof(dp));
    cout<<z(k,l,m,n)%mod;
}

         

Администратор Photo Автор: Администратор



Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться