ABC 026 C - 高橋君の給料
問題概要
省略
解法
上司から直属の部下に対して辺を張り、有向グラフを作成する。それを利用して、dfsを行う。部下がいないとき、つまり、グラフ上で葉の部分に該当する部下の給料は1なので、1を返す。部下が存在するとき、つまり、葉以外の頂点では、子の給料の最大値と最小値を計算して、最大値+最小値+1をかえせばよい。これを再帰関数で実装すればいい。
またループで解く方法もあり、数字の大きい人ほど、グラフ上で表したときに下側にいるので、ループを番号が大きい人から回すようにすればできる。
ミス
なし。
コード
再帰関数
#include <iostream> #include <cstdio> #include <cmath> #include <vector> #include <algorithm> using namespace std; typedef long long ll; #define rep(i,n) for(int i=0;i<(n);i++) const int INF = 1e9; int n; vector<int> G[22]; int dfs(int u){ int ma = 0, mi = INF; if(G[u].size() == 0){//葉 return 1; } for(auto v : G[u]){ ma = max(ma, dfs(v)); mi = min(mi, dfs(v)); } return ma + mi + 1; } int main(void){ cin >> n; for (int i = 1; i < n; ++i){ int b; cin >> b; b--; //b -> i G[b].push_back(i); } printf("%d\n", dfs(0)); return 0; }
ループで実装した場合
#include <iostream> #include <cstdio> #include <cmath> #include <vector> #include <algorithm> using namespace std; typedef long long ll; #define rep(i,n) for(int i=0;i<(n);i++) const int INF = 1e9; int n; vector<int> G[22]; int main(void){ cin >> n; for (int i = 1; i < n; ++i){ int b; cin >> b; b--; //b -> i G[b].push_back(i); } int dp[20];//dp[i] := i番目の社員の給料 //もらうdp for (int u = n - 1; u >= 0; --u){ if(G[u].size() == 0){ dp[u] = 1; continue; } int ma = 0, mi = INF; for(auto v : G[u]){ ma = max(ma, dp[v]); mi = min(mi, dp[v]); } dp[u] = ma + mi + 1; } printf("%d\n", dp[0]); return 0; }