[LA 6745 Traitor] 트리에 DP 덮어쓰기
https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=607&page=show_problem&problem=4757
분석하다.
클래식 트리에 DP 덮어쓰기
f[i][0]를 설정하면 i를 뿌리로 하는 자수를 나타낸다. i는 아들에게 덮이지 않고 아들의 최대치도 덮지 않는다.
f[i][1]을 설정하면 i를 뿌리로 하는 자수를 나타낸다. i는 아들에게 덮이지만 아들의 최대치를 덮지 않는다.
f[i][2]를 설정하면 i를 뿌리로 하는 자수를 나타낸다. i는 아들에게 덮어씌우지 않지만 아들의 최대치를 덮어씌운다.
f[i][3]를 설정하면 i를 뿌리로 하는 자수를 나타낸다. i는 아들에 의해 덮이고 아들의 최대치도 덮는다.
그러면
f[i][0]=sigma {f[j][0], f[j][1], f[j][2], f[j][3]}, j는 i의 아들
f[i][1]=max {sigma {f[j][0], f[j][1], f[j][2], f[j][3]}} +max {f[k][0], f[k][1]} +tag[i]}, k는 i의 어떤 아들이고 j는 i가 k를 제외한 아들이다.
f[i][2]=max {sigma {f[j][0], f[j][1], f[j][2], f[j][3]}} +max {f[k][0], f[k][2]} +tag[k]}, k는 i의 어떤 아들이고 j는 i가 k를 제외한 아들이다.
f[i][3]=max {sigma {f[j][0], f[j][1], f[j][2], f[j][3]}}}+max {f[p][0], f[p][1]}+tag[i]+max {f[q][0], f[q][2]}+tag[q]}, p와 q는 i의 어떤 아들이고 j는 p와 q를 제외한 아들이다.
3 전송의 경우 DP 1개로 수행
시간 복잡도 O (N)
코드
/**************************************************
* Problem: LA 6745
* Author: clavichord93
* State: Accepted
**************************************************/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
const int MAX_N = 10005;
const int MAX_E = 10005;
struct Edge {
int dest;
Edge *next;
Edge() {}
Edge(int _dest, Edge *_next) : dest(_dest), next(_next) {}
};
Edge EdgePool[MAX_E];
Edge *EP;
Edge *e[MAX_N];
int n, m;
int parent[MAX_N];
int tag[MAX_N];
int f[MAX_N][4];
int g[MAX_N];
int h[4];
inline void addedge(int a, int b) {
e[a] = new(EP++)Edge(b, e[a]);
}
void dp(int i) {
for (Edge *j = e[i]; j; j = j->next) {
dp(j->dest);
}
int sum = 0;
for (Edge *j = e[i]; j; j = j->next) {
sum += g[j->dest];
}
f[i][0] = sum;
f[i][1] = f[i][2] = f[i][3] = 0;
h[0] = h[1] = h[2] = h[3] = 0;
for (Edge *j = e[i]; j; j = j->next) {
f[i][1] = max(f[i][1], sum - g[j->dest] + max(f[j->dest][0], f[j->dest][1]) + tag[i]);
f[i][2] = max(f[i][2], sum - g[j->dest] + max(f[j->dest][0], f[j->dest][2]) + tag[j->dest]);
h[3] += g[j->dest];
h[3] = max(h[3], h[2] + max(f[j->dest][0], f[j->dest][1]) + tag[i]);
h[3] = max(h[3], h[1] + max(f[j->dest][0], f[j->dest][2]) + tag[j->dest]);
h[2] += g[j->dest];
h[2] = max(h[2], h[0] + max(f[j->dest][0], f[j->dest][2]) + tag[j->dest]);
h[1] += g[j->dest];
h[1] = max(h[1], h[0] + max(f[j->dest][0], f[j->dest][1]) + tag[i]);
h[0] += g[j->dest];
}
f[i][3] = h[3];
g[i] = max(max(f[i][0], f[i][1]), max(f[i][2], f[i][3]));
}
int main() {
#ifdef LOCAL_JUDGE
freopen("in.txt", "r", stdin);
#endif
while (scanf("%d %d", &n, &m), n || m) {
EP = EdgePool;
memset(e, 0, sizeof(e));
memset(f, 0, sizeof(f));
memset(g, 0, sizeof(g));
memset(tag, 0, sizeof(tag));
for (int i = 1; i <= n; i++) {
scanf("%d", &parent[i]);
if (parent[i]) {
addedge(parent[i], i);
}
}
for (int i = 1; i <= m; i++) {
int x;
scanf("%d", &x);
tag[x] = 1;
}
int ans = 0;
for (int i = 1; i <= n; i++) {
if (parent[i] == 0) {
dp(i);
ans += g[i];
}
}
printf("%d
", ans);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.