题解：P10755 [COI 2022-2023] Netrpeljivost

· · 题解

感觉这题需要一点“灵光一现”的能力，或者说是集中注意力？

注意到这一个题有一个很好的性质————它是一个满二叉树，这样假如我们对每一层做 n^2 的复杂度，那 \sum sz^2 也是 n^2 级别的。

然后我们就有了一个很显然的 n^4 的 dp ，我们设 f_{i,j} 表示在当前子树最左边的点为 i，最右边的点为 j 的最小值是多少，转移的时候分别枚举两个子树的左右端点就行了。

仔细想想这样转移其实很浪费，中间的点会用很多次，但每次都要重新枚举，我们可以先做一个中转。

把 f_{i,j} 看作左右端点间的边，把输入的 netrp(i,j) 看作左右子树间的边，可以先求出左子树的左端点到右子树的左端点的最短距离，这只需要枚举左子树的右端点，复杂度 n^3。同理可把右子树的左端点作为中转来求出最终结果，这样我们就有了一个 n^3 的做法。

这样可以做 512 但肯定做不了 2048。这时候就需要我们集中注意力了，上面的做法很难优化，但我们发现 2048 的子树就成了 1024 ，1024 的子树就是 512，显然我们可以直接做到 1024 这个子树，并且发现对于最后一层来说，我们并不关心最终的左右端点是什么，只需要求答案即可，那么直接套用一开始 n^4 的做法，不用枚举外面的左右端点，复杂度 n^2。

那么这题就做完了，复杂度 {\Theta(\frac{n}4}^3+\frac{n}2^2)。

代码。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
void ckmn(auto &x,auto y){if(x>y)x=y;}
const int N=2505;
int n,a[N][N];
struct Node{
    int l,r; ll w;
};vector<Node>s[N<<2];
ll vl1[N][N],vl2[N][N],w[N][N],mn1[N],mn2[N]; 
int a1[N],a2[N],a3[N],a4[N];
int t1,t2,t3,t4;
bool vs[N][N],v1[N],v2[N];
#define ls p<<1
#define rs p<<1|1   
void sol(int l,int r,int p){
    if(l==r){
        s[p].push_back({l,l,0});
        return;
    } int mid=l+r>>1;
    sol(l,mid,ls),sol(mid+1,r,rs);
    t1=t2=t3=t4=0;
    for(auto u:s[ls]){
        w[u.l][u.r]=u.w;
        if(!v1[u.l])a1[++t1]=u.l;
        if(!v2[u.r])a2[++t2]=u.r;
        v1[u.l]=v2[u.r]=true;
    }
    for(auto u:s[rs]){
        w[u.l][u.r]=u.w;
        if(!v1[u.l])a3[++t3]=u.l;
        if(!v2[u.r])a4[++t4]=u.r;
        v1[u.l]=v2[u.r]=true;
    }
    for(int i=1;i<=t2;++i)
        for(int j=1;j<=t3;++j)
            w[a2[i]][a3[j]]=a[a2[i]][a3[j]];
    for(int i=1;i<=t1;++i)
        for(int j=1;j<=t3;++j)
            for(int k=1;k<=t2;++k)
                ckmn(vl1[a1[i]][a3[j]],w[a1[i]][a2[k]]+w[a2[k]][a3[j]]);
    for(int i=1;i<=t1;++i)
        for(int j=1;j<=t4;++j)
            for(int k=1;k<=t3;++k)
                ckmn(vl2[a1[i]][a4[j]],vl1[a1[i]][a3[k]]+w[a3[k]][a4[j]]);
    for(int i=1;i<=t1;++i){
        for(int j=1;j<=t4;++j){
            s[p].push_back({a1[i],a4[j],vl2[a1[i]][a4[j]]});
            s[p].push_back({a4[j],a1[i],vl2[a1[i]][a4[j]]});
        }
    }
    for(auto u:s[ls])w[u.l][u.r]=w[0][0],v1[u.l]=v2[u.r]=false;
    for(auto u:s[rs])w[u.l][u.r]=w[0][0],v1[u.l]=v2[u.r]=false;
    vector<Node>().swap(s[ls]),vector<Node>().swap(s[rs]);
    for(int i=1;i<=t1;++i)for(int j=1;j<=t3;++j)
        vl1[a1[i]][a3[j]]=vl1[0][0];
    for(int i=1;i<=t1;++i)for(int j=1;j<=t4;++j)
        vl2[a1[i]][a4[j]]=vl2[0][0];
    for(int i=1;i<=t2;++i)for(int j=1;j<=t3;++j)
        w[a2[i]][a3[j]]=w[0][0];
}
signed main(){
    ios::sync_with_stdio(false);
    int i,j,k,l,r,x,y,z;
    for(i=1,cin>>n;i<=n;++i)
        for(j=1;j<=n;++j)cin>>a[i][j];
    memset(vl1,63,sizeof vl1);
    memset(vl2,63,sizeof vl2);
    memset(w,63,sizeof w);
    x=n+1>>1; ll ans=2e18;
    sol(1,x,2),sol(x+1,n,3); 
    for(i=1;i<=n;++i)mn1[i]=mn2[i]=vl1[0][0];
    for(auto u:s[2])ckmn(mn1[u.r],u.w);
    for(auto u:s[3])ckmn(mn2[u.l],u.w);
    for(i=1;i<=n;++i)for(j=1;j<=n;++j)
        ckmn(ans,mn1[i]+mn2[j]+a[i][j]);
    return printf("%lld\n",ans),0;
}