摆放棋子

#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
const int N=1e2+10,P=1e8;

int n1,n2,m1,m2;
int f[N][N][15][15];

int main()
{
    cin>>n1>>n2>>m1>>m2;
    
    f[0][0][0][0]=1;
    //由当前状态更新下一个状态，而不是由前一个状态更新当前状态
    //原因是因为 从当前状态的出边少，只有两个
    for(int i=0;i<=n1;i++)
    for(int j=0;j<=n2;j++)
    for(int k1=0;k1<=m1;k1++)
    for(int k2=0;k2<=m2;k2++)
    {
        if(k1!=0&&k2!=0) continue;//最后有连续k1个黑，k2个白，很显然不合理
        if(i+1<=n1&&k1+1<=m1)//k1==0或者k2==0
        f[i+1][j][k1+1][0]=(f[i+1][j][k1+1][0]+f[i][j][k1][k2])%P;
        if(j+1<=n2&&k2+1<=m2)//k1==0或者k2==0
        f[i][j+1][0][k2+1]=(f[i][j+1][0][k2+1]+f[i][j][k1][k2])%P;
    }
    int res=0;
    for(int i=1;i<=m1;i++)
    res=(res+f[n1][n2][i][0])%P;
    for(int j=1;j<=m2;j++)
    res=(res+f[n1][n2][0][j])%P;
    printf("%d",res);
    return 0;
}