anniversary/권영기

Difference between r1.2 and the current

@@ -91,3 +91,5 @@

}

}}}

====

[anniversary]

제출 결과 ¶

run-id user id 프로그램 명 결과 언어 경과 시간(초) 코드 사이즈(byte) 제출 시간
1370542 zeropage anniversary accept C++ 0.04 2110 2014-07-15 01:06

풀이 ¶

트리 구조를 반영하여 다이나믹을 구현해야 한다.
leaf-node(부하가 없는 직원)부터 친밀도를 구하여 root까지의 친밀도를 구해야 한다.
직속 관계에 있는 직원들은 같이 파티에 참석하지 못한다. -> 트리의 부모가 파티에 참석하면, 자식은 파티에 참석하지 못한다. 자식이 하나라도 파티에 참석하면 부모는 파티에 참석하지 못한다. 로 해석이 가능.
각 노드(직원)에 대해서 파티에 참석할 때의 최대 친밀도와 참석하지 않을 때의 최대 친밀도를 구한다.
점화식

d(idx,participate) = sum_of_not_participate + intimaices(idx);
d(idx,participate) = max(sum_of_participate, sum_of_not_participate);
DP 테이블을 채울 때는 leaf-node에서 root로 채워나가야 한다. -> 어떤게 leaf-node인지 판단하는게 필요.

소스 ¶

#include<iostream>
#include<algorithm>
#include<vector>
#include<list>
using namespace std;
const int N = 6020;
int n, intimacies[N];
int d[N][2]; // d[i][0] - participate, d[i][1] - not participate
int boss[N]; // at first, every staff's boss is himself. Thus boss[i] = i;
vector < list < int > > staffs; // vector[i]
vector < pair <int, int> > staff_priority_queue; // vector[i].first = level of Tree, vectors[i].second = idx.
int cmp(pair <int, int> s, pair <int, int> w){
	return s.first > w.first;
}
void leveling_node(int node, int level){
	staff_priority_queue[node].first = level;
	for(list<int>::iterator it = staffs[node].begin(); it != staffs[node].end(); it++){
		leveling_node(*it, level + 1);
	}
}
int main(void){

	cin>>n;
	staff_priority_queue.resize(n + 10);
	staffs.resize(n + 10);
	staff_priority_queue[0].first = -1;
	staff_priority_queue[0].second = -1;
	for(int i = 1; i<=n; i++){
		cin>>intimacies[i];
		staff_priority_queue[i].second = i;
		staff_priority_queue[i].first = -1;
		boss[i] = i;
	}
	int L, k, m = 0;
	while(1){
		cin>>L>>k;
		if(L == 0 && k == 0)break;
		staffs[k].push_back(L);
		staff_priority_queue[k].first++;
		boss[L] = k;
		//at the end, the root of subtree only satisfy 'boss[i] == i'.
		m++;
	};
	
        if(n == m){
		cout<<102;
		return 0;
	}//마지막 데이터 말도 안되는 거 처리를 위해서.. () 

	for(int i = 1; i<=n; i++){
		if(boss[i] == i){
			leveling_node(i, 0);
		}
	}

	int ans = -9999;
	sort(staff_priority_queue.begin(), staff_priority_queue.begin() + n + 1, cmp);
        //sorting by tree level.
	for(int i = 0; i<n; i++){
		int sum_of_participate = 0, sum_of_not_participate = 0;
		int idx = staff_priority_queue[i].second;
		for(list<int>::iterator it = staffs[idx].begin(); it != staffs[idx].end(); it++){
			if(d[*it][0] >= 0)sum_of_participate += d[*it][0];
			if(d[*it][1] >= 0)sum_of_not_participate += d[*it][1];
		}
		d[idx][0] = sum_of_not_participate + intimacies[idx];
		d[idx][1] = max(sum_of_participate, sum_of_not_participate);
		if(ans < d[idx][0])ans = d[idx][0];
		if(ans < d[idx][1])ans = d[idx][1];
	}
	cout<<ans;
        return 0;
}

anniversary