题解 P4253 【[SCOI2015]小凸玩密室】

· · 题解

T 「SCOI2015」小凸玩密室

题目

点这里

考场思路

题目读错了，导致我暴力都打不出来...

其实题目要求的是一定要将某一棵子树全部扫完再去扫其他的子树。

而不是左边扫一下，右边扫一下...

正解

首先，这里补充一个数据范围 （考试的时候也有）

对于 10\% 的数据，1≤n≤10；

另有 10\% 的数据， 1≤n≤20 ；

另有 10\% 的数据， 1≤n≤2000 ；

另有 20\% 的数据， 1≤n≤20000 ；

对于 100\% 的数据， 1≤n≤2\times 10^5 ， 1≤A_i≤10^5 ， 1≤B_i≤10^5 。

再次引用这句话 虽然是我自己编的

所谓信息竞赛，其实就是面向数据编程

其实，根据数据范围，一步一步想出算法并优化其实也是一个解题的好方法。

子方案 1 (10pts)

首先，看前 10\% 的数据，这个地方我们可以怎么做呢？

这样的暴力其实很简单，用 O(n!) 枚举我们访问的顺序。

再判断这个顺序是否合法，最后计算花费即可。

子方案 2 (20pts)

但是很明显，对于 10pts 的算法，是过不了第二个 10pts 的数据点的。

怎么进行优化？

注意到子方案 1 中有这样的操作：

随意枚举顺序，再判断是否合法。

这样做让我们用很多时间枚举了很多不合法的访问顺序。

那么我们是否可以让我们枚举的序列本来就合法，只需直接去算花费？

这是肯定可以的，时间复杂度 O(2^n)，因为我们要分左、右儿子去构造访问顺序。

这样，时间复杂度应该是 O(n2^n\cdot nlog^n_2)。

子方案 3 (50pts)

对于子方案 2 的优化显然是很好的，但是这都基于 暴力 这一思想，接下来我们需要转换思路。

考虑我们是怎么点亮一个子树的。

对于一个子树，它的根是 u，左儿子是 lc，右儿子是 rc。

假若我们先访问左子树，先不管它是怎么访问的。

那么，我们在左子树里面的访问顺序是否对后面的状态有影响？

是有的，证明如下： 本人数学不好，没有严格数学书写顺序

假设我们在左子树里面的访问顺序中的某一种是以 x 结尾。

很显然这个 x 有很多个。

而当我们从左子树到右子树去的时候，先要访问右子树的树根，即 rc。

那么这个花费显然是 dis(x,rc)*A[rc]。

而又因为这个 x 有很多个，那么很显然。不同的 x 是会有不同的花费。

因而左子树里面的访问顺序是对后面的状态有影响。

而且很显然，对后面状态有影响的只有最后访问的那个点在哪里。

所以，我们就可以定义状态 f[u][x] 为访问完以 u 为根的子树（不包含 u）且结尾在 x 时的最小花费。

那么，就可以分类进行状转：

很显然，状转中 x、y 都是需要循环枚举的，因而这个状转大概是 O(n^2) 的复杂度。

所以总复杂度是 O(n^3)。

但其实这样的计算是不准确的，准确复杂度应该是 \sum\frac{n^2}{2^{x+2}}。

这个复杂度是通过分层计算得出。

不难看出，这个复杂度可得到 50pts 的高分。

子方法 4 (正解)

我们发现，对于子方法三，其实已经快要过掉这道题了。

但是哪里的时间复杂度较高呢？

毋庸置疑的，状转的 O(n^2) 其实已经非常高了。

怎么减下来？肯定是要针对其状转简化。

观察状转：

我们先考虑其中一个状转，另一个其实是对应的。

拿第一个算式来说

f[u][y]=min\{dis(u,lc)\times A[lc]+f[lc][x]+dis(x,rc)\times A[rc]+f[rx][y]\}

考虑将其分解：

对于 dis(x,rc) ，其实不难看出

dis(x,rx)=dis(x,u)+dis(u,rc)

而这里面，只有 dis(x,u) 是改变的。

那么我们只需将 dis(x,u) 也存入状态中，就可以同时考虑它的最小值了。

所以，访问一边的最小花费就是

ans2=f[lc][x]+dis(u,rc)\times A[rc]+[dis(u,x)+dis(u,rc)]\times A[rc]

最后的花费，就是 ans2+f[lc][x] 了。

最后，根据这个 x 到底在左边还是在右边进行分类转移即可。

但是，这就是最后的答案了吗？

肯定不是，题目并未要求我们必须从 1 开始。

所以，定义另一个状态 t[i][j]：访问完 i 的子树，结尾在 j 时的最小花费。

那么这个怎么转移呢？

这里可以自行思考了

如果还是想不出来，看看代码吧，看看代码总有好处的

std version

#include<bits/stdc++.h>
#define mz 1000000007
using namespace std;

long long inf=mz*1LL*mz;
long long dep[200005];
int n,a[200005],b[200005];
vector <long long> dp[200005],dis[200005],dpp[200005];

void dfs(int x)
{
    dep[x]=dep[x/2]+b[x];//计算伪深度, 方便计算距离
    if(x*2<=n)//有左儿子
    {
        dfs(x*2);//先访问左儿子
        int t=dp[x*2].size();//得到左儿子的叶子共有多少个
        if(x*2+1<=n)//如果有右儿子
        {
            dfs(x*2+1);//访问右儿子
            long long ans1=inf,ans2=inf,ansp1=inf,ansp2=inf;
            //分别是 f, t
            for(int i=0;i<dp[x].size();i++)
            {
                if(i<t)//如果这个点是左子树上的点
                {

                    ans1=min(ans1,dp[x*2][i]+1LL*b[x*2]*a[x*2]+(dis[x][i]+b[x*2+1])*a[x*2+1]);
                    ansp1=min(ansp1,dpp[x*2][i]+dis[x][i]*a[x]+1LL*b[x*2+1]*a[x*2+1]);
                }
                else//当这个点是右子树上的点
                {
                    ans2=min(ans2,dp[x*2+1][i-t]+1LL*b[x*2+1]*a[x*2+1]+(dis[x][i]+b[x*2])*a[x*2]);
                    ansp2=min(ansp2,dpp[x*2+1][i-t]+dis[x][i]*a[x]+1LL*b[x*2]*a[x*2]);
                }
            }
            for(int i=0;i<dp[x].size();i++)
            {
                if(i<t)//如果它是左儿子
                {
                    dp[x][i]=ans2+dp[x*2][i];
                    dpp[x][i]=min(dp[x][i],ansp2+dp[x*2][i]);
                }
                else//是右儿子
                {
                    dp[x][i]=ans1+dp[x*2+1][i-t];
                    dpp[x][i]=min(dp[x][i],ansp1+dp[x*2+1][i-t]);
                }
            }
        }
        else//没有右儿子
        {
            for(int i=x;i>=1;i=i/2)
            {
                dp[i].push_back(0);
                dpp[i].push_back(0);
                dis[i].push_back(dep[x]-dep[i]);
            }
            dp[x][0]=1LL*b[x*2]*a[x*2];
            dpp[x][0]=inf;
            dp[x][1]=inf;
            dpp[x][1]=1LL*b[x*2]*a[x];
        }
    }
    else//没有后辈
    {
        for(int i=x;i>=1;i=i/2)
        {
            dp[i].push_back(0);
            dpp[i].push_back(0);
            dis[i].push_back(dep[x]-dep[i]);
        }
    }
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=2;i<=n;i++)
        scanf("%d",&b[i]);
    dfs(1);
    long long ans=inf;
    for(int i=0;i<dp[1].size();i++)
        ans=min(ans,dpp[1][i]);
    printf("%lld\n",ans);
    return 0;
}