SRM408: CandyGame

(問題概要)
acyclicなグラフ(|G| <= 50)に対して
操作: ノードに2つの飴があるとき、ひとつ食べて、ひとつを隣接ノードに移動
という操作が可能。
操作を繰り返して、目的のノードに飴を置くことが"できない"ようにする時に、最大何個飴を置けるか。

(解法)
少し考えると、目的のノードから遠いところに飴をおいたほうが良いことが分かる。
あとは分岐に対して全探索しつつ、メモ化再帰で適当に。

#include <numeric>
#include <map>
#include <cstdio>
typedef long long ll;

#define REP(i,n) for(int i=0; i<(int)(n); i++)

#include <queue>
#include <set>
#include <iostream>
#include <sstream>

using namespace std;

class CandyGame {
public:
  int maximumCandy(vector <string> graph, int target);
};

const int MAX = 1000;
int dist[50][50];
int n;
int t;
map<ll, ll> dp[50];

int solve(int pos, ll num){
  if(dp[pos].count(num)) return dp[pos][num];

  vector<int> v;

  REP(i,n) if(dist[pos][i] == 1 && dist[t][pos] + 1 == dist[t][i])
    v.push_back(i);

  const int cnt = v.size();

  if(cnt == 0) return dp[pos][num] = num;
  if(cnt == 1) return dp[pos][num] = solve(v[0], num * 2 + 1);

  ll ret = 0;

  vector<ll> memo(cnt);
  REP(i,cnt)
    memo[i] = solve(v[i], 1);

  const ll all = accumulate(memo.begin(), memo.end(), 0ll);
  REP(i,cnt){
    ll tmp = all - memo[i] + solve(v[i], num * 2 + 1);
    // cout << pos << " " << num << " " << v[i] << ": " << tmp << endl;
    ret = max(ret, tmp);
  }
  return dp[pos][num] = ret;
}

int CandyGame::maximumCandy(vector <string> graph, int target){
  n = graph.size();
  t = target;
  REP(i,n) dp[i].clear();
  REP(i,n) REP(j,n) dist[i][j] = graph[i][j] == 'Y' ? 1 : MAX;
  REP(i,n) dist[i][i] = 0;
  REP(k,n) REP(i,n) REP(j,n)
    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
  REP(i,n) if(dist[target][i] == MAX)
    return -1;
  ll ans = solve(target, 0);
  return ans < 2000000000 ? ans : -1;
}