HDU 6065 RXD, tree and sequence （LCA, 2017 Multi-Univ Training Contest 3）

Problem

有根树 T 有 N 个节点，根节点标号为 1 ，深度为 1 。

特定序列 P 有 N 个不同数字 (1~N) 。

定义每个块的深度为块中所有点的最近公共祖先的深度。

求将 P 序列划分成 K 个连续的块，使得 K 块的深度和最小，问最小深度和 ?

Limit

1≤k≤n≤3×105

n×k≤3×105

Idea

对于任意连续序列的 LCA ，一定是序列任意两个相邻数 LCA 中深度最小的一组 lca(i, i+1) 。

因此，用 dp[k][i] 表示将序列前 i 个数划分为 k 块的最小深度和。

状态转移为:

• dp[k][i] = min(dp[k][i], dp[k][i-1]) 如果认为 pi 不是第 k 块中导致 LCA 深度最小的相邻数。
• dp[k][i] = min(dp[k][i], dp[k-1][i-1]) 如果认为单点 pi 即为第 k 块中的深度最小点。
• dp[k][i] = min(dp[k][i], dp[k-1][i-2]) 如果将 pi−1 和 pi 作为第 k 块导致 LCA 最小的相邻数。

思路参考自某大佬

貌似在 VJudge 的提交中发现了 O(N×K2) 的 AC 代码。结合标准数据发现 6 组 K 都在 10 左右…呵呵

Code

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 500000 + 10;
const int inf = 2e9;
int N, K, p[MAXN], head[MAXN], cnt, dp[MAXN];
struct Edge {
int nxt, to;
} e[MAXN * 2];
void addedge(int u, int v) {
e[++cnt].nxt = head[u];
e[cnt].to = v;
head[u] = cnt;
}
const int maxh = 20;
int dep[MAXN];
int anc[MAXN][maxh];
void dfs(int rt) {
static int Stack[MAXN];
int top = 0;
dep[rt] = 1;
for(int i=0;i<maxh;i++)
anc[rt][i] = rt;
Stack[++top] = rt;
while(top) {
int x = Stack[top];
if(x != rt) {
for(int i=1, y;i<maxh;i++)
y = anc[x][i-1],
anc[x][i] = anc[y][i-1];
}
for(int &i=head[x];i;i=e[i].nxt) {
int y = e[i].to;
if(y != anc[x][0]) {
dep[y] = dep[x] + 1;
anc[y][0] = x;
Stack[++top] = y;
}
}
while(top && head[Stack[top]] == 0) top--;
}
}
void swim(int &x, int H) {
for(int i=0;H;i++) {
if(H & 1)
x = anc[x][i];
H /= 2;
}
}
int lca(int x, int y) {
int i;
if(dep[x] > dep[y]) swap(x, y);
swim(y, dep[y]-dep[x]);
if(x == y)
return dep[x];
for(;;) {
for(i=0;anc[x][i] != anc[y][i];i++);
if(i == 0)
return dep[anc[x][0]];
x = anc[x][i-1];
y = anc[y][i-1];
}
printf("Errorn");
return -1;
}
inline int toInt(int k, int i) {
return k * (N+1) + i;
}
int main()
{
while(scanf("%d %d", &N, &K)!=EOF)
{
memset(anc, 0, sizeof(anc));
memset(head, 0, sizeof(head));
memset(dp, 0, sizeof(dp));
cnt = 0;
for(int i=1;i<=N;i++)
scanf("%d", &p[i]);
for(int i=1, u, v;i<N;i++)
{
scanf("%d %d", &u, &v);
addedge(u, v);
addedge(v, u);
}
dfs(1);
for(int i=1;i<=N;i++)
for(int k=0, mn;k<=K;k++)
{
mn = 0x3f3f3f3f;
if(k > i)
break;
if(i-1 >= k)
mn = min(mn, dp[toInt(k, i-1)]);
if(i-1 >= k-1 && k-1>=0)
mn = min(mn, dp[toInt(k-1, i-1)] + dep[ p[i] ]);
if(i-2 >= k-1 && i-1>0 && k-1>=0)
mn = min(mn, dp[toInt(k-1, i-2)] + lca(p[i], p[i-1]));
dp[toInt(k, i)] = mn;
}
printf("%dn", dp[toInt(K, N)]);
}
}

最后

以上就是机智小笼包为你收集整理的HDU 6065 RXD, tree and sequence （LCA, 2017 Multi-Univ Training Contest 3）的全部内容，希望文章能够帮你解决HDU 6065 RXD, tree and sequence （LCA, 2017 Multi-Univ Training Contest 3）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。