Problem F
Busy Programmer
Input: Standard Input

Output: Standard Output

Our famous programmer Gordov Mia (Mr. Donkey) is having a very busy time in his office. His erratic boss has assigned him to two projects (project MICRO & project GOO) at the same time. Consequently, problems have occurred while making a feasible work schedule for him. The boss needs to submit a report to the CEO specifying the schedule of work for all the resources working under him for a period of 2D days. Gordov must work D days on each project. He doesn’t work more than a single project on a particular day. Gordov must finish the work of the project he started earlier (i.e. on the first day of the schedule) first. As the progress of both the projects depends on him, he can not be away from any project for more than G consecutive days. (of course unless a project is already complete.) For example, if D = 3 & G = 2, there can be ten valid schedules,

Now, Given D & G, you are to determine the number of possible schedules with the given constraints.

Input

There are around 2400 test cases in the input file. Every test case has two non-negative integers, D & G (D,G<=33) on a line by itself. A case with D = G = -1 terminates the input. This case must not be processed.

Output

For each test case, print a line in the format “Case x: y” where x is the case number & y is the number of possible schedules.

Sample Input                               Output for Sample Input                                    

Problemsetter: Mohammad Mahmudur Rahman

Special Thanks: Abdullah al Mahmud (Satej)

題目描述：

現在有兩個工作，各耗費 D 天完成，兩個工作可以交替執行，每天只值行一種，

因此會用 2*D 天完成兩個工作，但相同工作之間最多間隔 G 天。

如果其中一個工作完成後，另一個工作可以連續工作超過 G 天。

問有多少排列方式。

題目解法：

考慮 dp[i][j][k][2] 表示 i 天，此時其中一個工作已經工作 j 天、k 天，

並且上一個工作種類是什麼。

在轉移的時候，窮舉下一個工作天數 <= G，並且特別考慮其中一個工作已經完成的情況。

#include <stdio.h>
#include <algorithm>
using namespace std;

int main() {
    int D, G;
    int i, j, k;
    int cases = 0;
    while(scanf("%d %d", &D, &G) == 2 && D != -1) {
        long long dp[70][35][35][2] = {};
        for(i = 1; i <= G; i++)
            dp[i][i][0][0] = 1;
        for(i = 1; i <= 2*D; i++) {
            for(j = 0; j <= i; j++) {
                for(k = 1; k <= G; k++) {
                    if(j+k <= D && i-j <= D)
                        dp[i+k][j+k][i-j][0] += dp[i][j][i-j][1];
                    if(i-j+k <= D && j <= D)
                        dp[i+k][j][i-j+k][1] += dp[i][j][i-j][0];
                }
                if(j == D && D-(i-j) > G)
                    dp[2*D][D][D][1] += dp[i][j][i-j][0];
            }
        }
        printf("Case %d: %lld\n", ++cases, dp[2*D][D][D][1]*2);
    }
    return 0;
}