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; }