Pretty Awesome DP question (and basic :D )
Question :
Gaius Julius Caesar, a famous general, loved to line up his soldiers. Overall the army had n1 footmen and n2 horsemen. Caesar thought that an arrangement is not beautiful if somewhere in the line there are strictly more that k1 footmen standing successively one after another, or there are strictly more than k2 horsemen standing successively one after another. Find the number of beautiful arrangements of the soldiers.
Note that all n1 + n2 warriors should be present at each arrangement. All footmen are considered indistinguishable among themselves. Similarly, all horsemen are considered indistinguishable among themselves.
Input
The only line contains four space-separated integers n1, n2, k1, k2 (1 ≤ n1, n2 ≤ 100, 1 ≤ k1, k2 ≤ 10) which represent how many footmen and horsemen there are and the largest acceptable number of footmen and horsemen standing in succession, correspondingly.
Output
Print the number of beautiful arrangements of the army modulo 100000000 (108). That is, print the number of such ways to line up the soldiers, that no more than k1 footmen stand successively, and no more than k2 horsemen stand successively.
input
2 1 1 10
output
1
input
2 3 1 2
output
5
HOW TO CRACK THIS QUESTION :
I think this problem was easier than C, to be honest. K1 and K2 were very low (<= 10) . I am not sure why. But there is a dp solution.
Let us say that we have r1 footmen and r2 horsemen left to place. The previous lastn positions, contain footmen or horsemen depending of the value of a variable lasttype, if lasttype = 1, then the previous lastn positions contain horsemen. So, we in fact remember the contents of the previous positions, we just have to make sure that lastn does not ever exceed k1 or k2 depending on whether they are footmen or horsemen.
Let f(r1,r2,lasttype, lastn) the total number of ways to solve that sub-problem. The final result will be f(n1,n2, 0,0) (There are n1 footmen to place, n2 horsemen, and we can pretend that there are 0 footmen in the previous positions). So, let us think of transitions:
* At each position, we can place a footman, or a horseman. Depending on what we do, we increase lastn or set (lastype = 1, lastn = 1) in case we placed a different type of unit than the previous one.
Let us say that we have r1 footmen and r2 horsemen left to place. The previous lastn positions, contain footmen or horsemen depending of the value of a variable lasttype, if lasttype = 1, then the previous lastn positions contain horsemen. So, we in fact remember the contents of the previous positions, we just have to make sure that lastn does not ever exceed k1 or k2 depending on whether they are footmen or horsemen.
Let f(r1,r2,lasttype, lastn) the total number of ways to solve that sub-problem. The final result will be f(n1,n2, 0,0) (There are n1 footmen to place, n2 horsemen, and we can pretend that there are 0 footmen in the previous positions). So, let us think of transitions:
* At each position, we can place a footman, or a horseman. Depending on what we do, we increase lastn or set (lastype = 1, lastn = 1) in case we placed a different type of unit than the previous one.
const int MOD = 100000000;
int n1, n2, k1, k2;
int mem[101][101][2][11];
int count(int r1, int r2, int lasttype, int lastn) {
int & c = mem[r1][r2][lasttype][lastn];
if (c == -1) {
c = 0;
// place r1
if (r1 > 0) {
if (lasttype == 1) {
c += count(r1-1,r2,0,1);
} else if (lastn < k1) {
c += count(r1-1,r2,0,lastn+1);
}
}
//place r2
if (r2 > 0) {
if (lasttype == 0) {
c += count(r1,r2-1,1,1);
} else if (lastn < k2) {
c += count(r1,r2-1,1,lastn+1);
}
c %= MOD;
}
if (r1 == 0 && r2 == 0) {
//all done!
c = 1;
}
}
return c;
}
int solve()
{
memset(mem,-1,sizeof(mem));
return count(n1, n2, 0,0);
}
