ドワンゴ 予選 D - ディスクの節約

• 問題

問題概要

N個のtask,そのメモリ使用x[i] (1<=i<=N), タスク依存関係a[i] (2<=i<=N) が与えられる.
iのタスクはa[i]のタスク実行後にしか実行できず,その中でもタスク1は他の全てのタスク実行後にしか実行できない.
メモリx[i]はタスクi実行後に消すことができる.タスク実行に必要なメモリ最大値を求めよ.
1<=N<=20, 1<=xi<=10⁶

解法

制約からbitDPっぽい.
タスクiのメモリが残っているか(1<=i<=N)をiビット目で表して,その時のメモリを表す.
状態->メモリ使用量は2^N * N²で求めておくことができる.(状態遷移を用いると2^Nでできそう)
状態1(タスク1のメモリだけ残っている状態)に達するまでに使用したメモリ使用量の最大値,の最小値をmemo[state]で表す.
後はstateの内で立っているbit(実行済みのタスク・親)を一つ選んでそのタスクを実行するために必要な依存先のタスク(子)を実行した時の状態に戻す.
その状態時のコストと,その状態から親を消した(親を実行する前の)状態に達するまでの最大コストを,各親タスクについて求める.
その中で最小のものが求めるmemo[state]となる.
後はメモ化探索する.
コストはO(2^N * N²)で結構不安だったが,まあ間に合った.

メモ

DFSでやってWAした.
時間後に自力ACできたのでかなり後悔...

コード

#include "bits/stdc++.h"

#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define pb push_back
#define DEBUG false

using namespace std;

using ll = long long;
using P = pair<int,int>;
using Pl = pair<int,ll>;

const int mod=1e9+7,INF=1<<30;
const double EPS=1e-12,PI=3.1415926535897932384626;
const ll LINF=1LL<<60;
const int MAX_N = 21;
const ll lmod = 1e9+7;

ll x[MAX_N],sumx[1<<21],memo[1<<21];
vector<int> graph[MAX_N];
int N;

ll solve(int state){
  if(memo[state]>=0LL) return memo[state];
  ll res = LINF;
  rep(i,N){
    // 立っているbitを選んで子を立たせる
    if(((1<<i)&state)==0) continue;
    int next = state;
    for(auto u:graph[i]) next |= (1<<u);
    // cout << "next = " << next << endl;
    res = min(res,max(sumx[next],solve(next^(1<<i))));
  }
  // cout << "res = " << res << endl;
  return memo[state] = res;
}

int main(){
  cin >> N ;
  rep(i,N) cin >> x[i] ;
  rep(i,N-1){
    int a; cin >> a ;
    graph[a-1].pb(i+1);
  }
  fill(memo,memo+(1<<N),-1LL);
  memo[0] = 0LL;
  rep(i,1<<N){
    rep(j,N) if((i&(1<<j))!=0) sumx[i] += x[j];
  }
  cout << solve(1) << endl;
  return 0;
}