UVa11432 Busy Programmer

解法

dp[MICROの作業をした日数][GOOの作業をした日数][連続日数][現在取りかかっているプロジェクト 0 or 1] := パターン数

としてメモ化再帰。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int D, G;
ll memo[35][35][35][2];

ll solve(int mfin, int gfin, int cdays, int p) {
  
  //cout << mfin << " " << gfin << " " << cdays << " " << p << endl;
  
  ll &ret = memo[mfin][gfin][cdays][p];
  if(ret >= 0) return ret;
  
  if(mfin == D) return ret = 1;
  if(gfin == D) return ret = 0;
  
  ret = 0;
  
  if(p == 0) {
    if(cdays < G) {
      ret += solve(mfin+1, gfin, cdays+1, p);
    }
    ret += solve(mfin, gfin+1, 1, !p);
  }
  else {
    if(cdays < G) {
      ret += solve(mfin, gfin+1, cdays+1, p);
    }
    ret += solve(mfin+1, gfin, 1, !p);
  }
  
  return ret;
}

int main() {
  
  int Tc = 1;
  while(cin >> D >> G && (~D|~G)) {
    ll ans;
    if(D == 0) {
      ans = 1;
    }
    else if(G == 0) {
      ans = 0;
    }
    else {
      memset(memo, -1, sizeof memo);
      ans = solve(1, 0, 1, 0) * 2;
    }
    
    cout << "Case " << Tc++ << ": " << ans << endl;
  }
  
  return 0;
}