RXD, tree and sequence IN HDU6065

　　解这道题绕了好多弯路。。。先是把"depth of the least common ancestor"这句话忽视掉，以为是最深点与最浅点的深度差；看到某人题解（的开头）之后发现自己理解错误，修改思路。结果又是绕好多弯路。构造了一个式子dp[i,j]其中i是前几个点，j是切分的段数。一直以为转移是整段转移（如果段是(1,5)，直接dp[5,j]=dp[0,j-1]+val(1,5)），但是发现时间复杂度又过高，o(nk*n)，之后改变了下思路，发现这题的整段真正有用的是最小深度那个核。

　　题意是把一串n排列切分成k段，让里面的数计算这些对应结点的最近公共祖先深度，之后求这个最小深度总和。如(1) (5 2 4 3)，第1段是1的深度，第2段是min( dep(lca(5,2)) , dep(lca(2,4)) , dep(lca(4,3)) )，其中的核就是最小的那个deplca。

　　dp转移不需转移整段，可以空转移，只要保证加上那个核的权值之后跳到下一段就行，这样转移步幅小了很多（1~2），dp次数也降为o(nk)

　　dp[i,j]=dp[i-1,j]（把i这个点当成对答案无关的跳过）dp[i-1,j-1]（把i这个点当成对答案有关的核转移）dp[i-2,j-1]（把i-1和i的最近公共祖先当成对答案有关的核转移）

　　这里的代码很无耻地借鉴了autsky-jadek的。。。

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#define min(a,b) (a<b?a:b)
using namespace std;
typedef pair<int,int> Point;
const int N=300005;
int a[N],head[N],to[N<<1],nxt[N<<1],lca[N],fa[N],dep[N],ans[N],arc[N];
bool vis[N];
int n,k,u,v,en;
int dp[N+100000];

void addedge(int u,int v)
{
    to[en]=v;
    nxt[en]=head[u];
    head[u]=en++;
}
int find_(int x){
    return x==fa[x] ? x : fa[x]=find_(fa[x]);
}
void LCA(int u,int nowdeep)
{
    ans[u]=u;
    dep[u]=nowdeep;
    for(int i=head[u];i!=-1;i=nxt[i]) if(!dep[to[i]])
    {
        LCA(to[i],nowdeep+1);
        int f1=find_(u),f2=find_(to[i]);
        fa[f1]=f2;
        ans[find_(u)]=u;
    }
    vis[u]=true;
    if(u!=0 && vis[u-1])
        lca[u-1]=ans[find_(u-1)];
    if(u!=n-1 && vis[u+1])
        lca[u]=ans[find_(u+1)];
}
int main()
{
    int tmp,i;
    while(scanf("%d%d",&n,&k)!=EOF)
    {
        en=0;
        memset(vis,0,sizeof(vis));
        memset(dep,0,sizeof(dep));
        memset(head,-1,sizeof(head));
        memset(dp,0,sizeof(dp));
        for(i=0;i<n;i++)
        {
            scanf("%d",&tmp);
            arc[tmp]=fa[i]=i;
        }
        for(i=1;i<n;i++)
        {
            scanf("%d%d",&u,&v);
            addedge(arc[u],arc[v]);addedge(arc[v],arc[u]);
        }
        LCA(arc[1],1);
        for(i=0;i<n-1;++i)
            lca[i]=dep[lca[i]];
        for(i=1;i<=n;++i)
        {
            int top=min(i,k);
            for(int j=0;j<=top;++j)
            {
                int nowans=99999999;
                if(j>0&&i>0)
                    nowans=min(nowans,dp[(i-1)*(k+1)+j-1]+dep[i-1]);
                if(i-2>=0&&j-1>=0&&j-1<=i-2)
                    nowans=min(nowans,dp[(i-2)*(k+1)+j-1]+lca[i-2]);
                if(j<=i-1)
                    nowans=min(nowans,dp[(i-1)*(k+1)+j]);
                dp[i*(k+1)+j]=nowans;
            }
        }
        printf("%d\n",dp[n*(k+1)+k]);
    }
    return 0;
}

View Code

　　tarjan离线，全局求祖先，顺带把相邻数字全查了

RXD, tree and sequence IN HDU6065

推荐阅读