제출 결과 ¶
run-id user id 프로그램 명 결과 언어 경과 시간(초) 코드 사이즈(byte) 제출 시간
1370542 zeropage anniversary accept C++ 0.04 2110 2014-07-15 01:06
1370542 zeropage anniversary accept C++ 0.04 2110 2014-07-15 01:06
풀이 ¶
- 트리 구조를 반영하여 다이나믹을 구현해야 한다.
- leaf-node(부하가 없는 직원)부터 친밀도를 구하여 root까지의 친밀도를 구해야 한다.
- 직속 관계에 있는 직원들은 같이 파티에 참석하지 못한다. -> 트리의 부모가 파티에 참석하면, 자식은 파티에 참석하지 못한다. 자식이 하나라도 파티에 참석하면 부모는 파티에 참석하지 못한다. 로 해석이 가능.
- 각 노드(직원)에 대해서 파티에 참석할 때의 최대 친밀도와 참석하지 않을 때의 최대 친밀도를 구한다.
- 점화식
- 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;
}
