CF 118D Caesar‘s Legions（记忆化搜索）

直接上代码和注释：

//记忆化搜索
//题意：
//有n个步兵，m个骑兵，步兵最多连续站k1个，骑兵最多连续站k2个，问多少种站法
#include<bits/stdc++.h>using namespace std;
#define int long long
const int N = 110, mod = 100000000;
int memo[2][N][N];//记忆化数组 记录步兵剩余j个 骑兵剩余k个 最后为i兵种 的方案数
int n, m, k1, k2;
int ans;int dfs(int x)//x代表当前这个位置准备放什么
{int& res = memo[x][n][m];	//简化写法，设置一个记忆化数组的引用变量if (~res) {//若当前不为空则返回已经有的数值return res;}if (!n && !m) return res = 1;	//若两者均为空，则表示有一种情况了res = 0;int cnt = (!x ? min(n, k1) : min(m, k2));for (int i = 1; i <= cnt; ++i) {//循环枚举这个位置连续放多少个相同的士兵int& one = (!x ? n : m);one -= i;res += dfs(x ^ 1), res %= mod;one += i;}return res;
}signed main()
{cin >> n >> m >> k1 >> k2;memset(memo, -1, sizeof memo);//将所有方案分为两类，0表示第一个位置即将放置footman，1表示第一个位置即将放置horsemanans = (dfs(0) + dfs(1)) % mod;cout << ans << '\\n';return 0;
}