[조이2008] 기사.
3208 단어 2008
주로 모든 기사가 가지고 있고 유일하게 자신이 가장 싫어하는 기사가 있다.
그래서 전체 그림은 여러 개의 연결 블록이고 모든 연결 블록은 하나의 고리와 나무이다.
먼저 나무에 dp를 만들고,
두 개의 고리를 매거하여 각각 찾지 않을 수 있다.
링 dp도 쓸 수 있어요.
(나는 링 dp라고 썼다)
/**
* Problem:[ZJOI2008]p5
* Author:Shun Yao
* Time:2013.5.30
* Result:Accepted
* Memo:DP
*/
#include <cstring>
#include <cstdio>
const long Maxn = 1000005;
long long max(long long x, long long y) {
return x > y ? x : y;
}
void swap(long &x, long &y) {
x ^= y;
y ^= x;
x ^= y;
}
long n, A[Maxn], fa[Maxn], ff[Maxn];
long long ans, f[Maxn][2];
class gnode {
public:
long v;
gnode *next;
gnode() {}
~gnode() {}
gnode(long V, gnode *ne):v(V), next(ne) {}
} *g[Maxn];
void add(long x, long y) {
g[x] = new gnode(y, g[x]);
g[y] = new gnode(x, g[y]);
}
void DP_Tree(long x) {
static long q[Maxn], *l, *r;
static gnode *e;
r = (l = &(*q = x)) + 1;
while (l != r) {
for (e = g[*l]; e; e = e->next) if (!ff[e->v]) {
ff[e->v] = *l;
*(r++) = e->v;
}
++l;
}
do {
--l;
f[*l][0] = 0;
f[*l][1] = A[*l];
for (e = g[*l]; e; e = e->next) if (ff[e->v] == *l) {
f[*l][0] += f[e->v][1];
f[*l][1] += f[e->v][0];
}
f[*l][1] = max(f[*l][1], f[*l][0]);
} while (l != q);
}
long q[Maxn], *l, *r;
long st[Maxn << 1], stl;
long ST[Maxn], STl;
long d[Maxn];
long long h[Maxn];
void DP(long x) {
static gnode *e;
static long a, b;
r = (l = &(*q = x)) + 1;
fa[x] = -1;
stl = 0;
STl = 0;
while (l != r) {
for (e = g[*l]; e; e = e->next) if (e->v != fa[*l]) {
if (!fa[e->v]) {
d[e->v] = d[*l] + 1;
fa[e->v] = *l;
*(r++) = e->v;
} else if (!stl) {
a = *l;
b = e->v;
if (d[a] < d[b])
swap(a, b);
while (d[a] > d[b]) {
st[++stl] = a;
a = fa[a];
}
while (a != b) {
st[++stl] = a;
ST[++STl] = b;
a = fa[a];
b = fa[b];
}
st[++stl] = a;
while (STl)
st[++stl] = ST[STl--];
}
}
++l;
}
static long i;
for (i = 1; i <= stl; ++i)
ff[st[i]] = -1;
for (i = 1; i <= stl; ++i)
DP_Tree(st[i]);
static long long ret;
h[0] = 0;
h[1] = f[st[1]][1];
for (i = 2; i < stl; ++i)
h[i] = max(h[i - 2] + f[st[i - 1]][0] + f[st[i]][1], h[i - 1] + f[st[i]][0]);
ret = h[stl - 1] + f[st[stl]][0];
h[1] = 0;
h[2] = f[st[2]][1];
for (i = 3; i <= stl; ++i)
h[i] = max(h[i - 2] + f[st[i - 1]][0] + f[st[i]][1], h[i - 1] + f[st[i]][0]);
ans += max(h[stl] + f[st[1]][0], ret);
}
int main() {
static long i, B;
freopen("p5.in", "r", stdin);
freopen("p5.out", "w", stdout);
scanf("%ld", &n);
for (i = 1; i <= n; ++i)
g[i] = 0;
for (i = 1; i <= n; ++i) {
scanf("%ld%ld", A + i, &B);
add(i, B);
}
memset(d, 0, sizeof d);
memset(fa, 0, sizeof fa);
memset(ff, 0, sizeof ff);
ans = 0;
for (i = 1; i <= n; ++i)
if (!fa[i])
DP(i);
printf("%lld", ans);
fclose(stdin);
fclose(stdout);
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
bzoj 1042 HAOI 2008 코인 쇼핑이 문제의 사고방식은 신이다. 우선 제한이 없는 방안의 수를 dp로 낸다. dp 할 때 주의 먼저 순환 1...4 번 더. 1 번.maxs 중복 방지.경계는 f[0] = 1입니다.이렇게 기초적인 가방은 다 까먹었어 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.