118D – Caesar’s Legions

A Dynamic Programming problem.
You’re trying to find the number of permutations of footmen/horsemen that match the given criterion. While you’re permuting, some problems are revisited. That’s when DP comes in handy:

• State S(n1, n2, k1, k2) – You’ve placed n1 footmen and n2 horsemen. The previous soldier is either a part of k1 consecutive footmen or k2 consecutive horsemen.
• Transition S(n1, n2, k1, k2) = S(n1 + 1, n2, k1 + 1, 0) + S(n1, n2 + 1, 0, k2 + 1) – You can either place a footman — which increases the number of consecutive footmen by one and resets the number of consecutive horsemen k2 — or a horseman.

Caution!

• Don’t forget the modulo 10⁸.

C++ implementation but with values decreasing instead of increasing:

#include <iostream>
#include <cstring>
using namespace std;

#define N 128
#define K 16
#define M 100000000

int nWays[N][N][K][K];
int N1, N2, K1, K2;

long long getNWays(int n1, int n2, int k1, int k2) {
	if (n1 < 0 || n2 < 0 || k1 < 0 || k2 < 0)
		return 0;
	if(n1 == 0 && n2 == 0)
		return 1;
	if (nWays[n1][n2][k1][k2] != -1)
		return nWays[n1][n2][k1][k2];
	return nWays[n1][n2][k1][k2] =
			(getNWays(n1 - 1, n2, k1 - 1, K2) + getNWays(n1, n2 - 1, K1, k2 - 1)) % M;
}

int main() {
	memset(nWays, -1, sizeof nWays);
	cin >> N1 >> N2 >> K1 >> K2;
	cout << getNWays(N1, N2, K1, K2) << endl;
	return 0;
}