这个问题可以通过懒惰动态规划来解决。设 $\text{dp}[n1][n2][2]$ 表示在凯撒的军团中放置士兵的方案数。参数定义如下：

• $n1$ 表示步兵的数量
• $n2$ 表示骑兵的数量
• 第三个参数表示凯撒在队伍开头放置的是哪种士兵

如果凯撒想要放置步兵，那么状态 $\text{dp}[n1][n2][0]$ 会转移到状态 $\text{dp}[n1 - i][n2][0]$，其中 $0 \le i \le \min(k1, n1)$。

如果凯撒想要放置骑兵，那么状态 $\text{dp}[n1][n2][1]$ 会转移到状态 $\text{dp}[n1][n2 - i][1]$，其中 $0 \le i \le \min(k2, n2)$。

#include <bits/stdc++.h>
using namespace std;
 
int n1,n2,FC,Hc,x;
int dp[105][105][11][11];
int call(int i,int j,int x,int y){
 
    if( i<0 || j<0 || x>FC || y>Hc ) return 0;
    if(i+j==0) return 1;
 
    if(dp[i][j][x][y]!=-1) return dp[i][j][x][y];
 
    return dp[i][j][x][y] = (call(i-1,j,x+1,0)+ call(i,j-1,0,y+1))%100000000;
 
}
 
 
int main(){
    memset(dp,-1,sizeof(dp));
    cin>>n1>>n2>>FC>>Hc;
    cout<<call(n1,n2,0,0);
 
}