ABC026_C
※bukaという変数とkouhaiという変数が混ざって大変汚いコード
部下と上司の木を表現してある社員が部下を持たなければ1,
部下を持っていればその部下の中からmax(部下の給料)+min(部下の給料)+1を返す.
メモ化再起風に解いた.
#include <bits/stdc++.h> using namespace std; static const int MAX_N = 20; struct Node{ vector<Node*> kouhai; int kyuuryou; }; Node worker[MAX_N]; int solve(Node *p) { /* 引数(Node*) : 社員 返り値(int) : 給料 worker[num].kyuuryou */ if((int)p->kouhai.size()==0){//部下がいなければ //給料を1にセットしてから給料1を返す p->kyuuryou = 1; return 1; }else{//部下がいれば //部下全員の給料を求めmax(部下の給料)+min(部下の給料)+1を返す vector<int> buka_kyuuryou; int max_kyuuryou = INT_MIN; int min_kyuuryou = INT_MAX; for(int i=0;i<(int)p->kouhai.size();i++){ int tmp = solve(p->kouhai[i]);//部下p->kouhai[i]の給料 buka_kyuuryou.push_back(tmp); max_kyuuryou = max(tmp,max_kyuuryou); min_kyuuryou = min(tmp,min_kyuuryou); } p->kyuuryou = max_kyuuryou+min_kyuuryou+1; return p->kyuuryou; } } int main() { int n,x; cin>>n; for(int i=1;i<n;i++){ cin>>x; worker[x-1].kouhai.push_back(&worker[i]);//社員iの先輩は社員x-1 == 社員x-1の後輩は社員i } solve(&worker[0]); int ans = worker[0].kyuuryou; cout<<ans<<endl; return 0; }
より簡単な方法
部下が上司より後になるのを利用して後ろから計算していく.
int P[MAX_N];//給料 int minP[MAX_N];//部下の給料の最小値 int maxP[MAX_N];//部下の給料の最大値 int sub[MAX_N];//部下の人数 for(int i=N-1;i>=0;i--){ if(sub[i].size()==0){//部下が0人ならば P[1]=1;//給料は1 continue; } //部下がいるならば部下の中で最大+最小+1 maxP[i] = 0; minP[i] = (int)1e9; for(int j=0;j<(sub[i].size();j++){ maxP[i] = max(maxP[i],P[j]); minP[i] = min(minP[i],P[j]); } P[i] = maxP[i] + minP[i]; }