1 条题解

  • 0
    @ 2025-7-17 22:20:24
    #include <cstdio>
    #include <cstring>
    #include <cstdlib>
    #include <iostream>
    #include <cmath>
    using namespace std;
    int n,m,p,a[150],b[150],c[150],xz[150][150],xy[150][150],yz[150][150],ans,tt;
    void read()
    {
        scanf("%d%d%d",&m,&n,&p);
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        for(int i=1;i<=m;i++) scanf("%d",&b[i]);
        for(int i=1;i<=p;i++) scanf("%d",&c[i]);
        for(int i=0;i<150;i++)
            for(int j=0;j<150;j++)
                xz[i][j]=xy[i][j]=yz[i][j]=999999;
        ans=999999;
    }
    
    void go()
    {
        xz[0][p+1]=0;
        for(int i=1;i<=n;i++)
            for(int j=p;j>=1;j--)
                xz[i][j]=min(min(xz[i-1][j+1],xz[i-1][j]),xz[i][j+1])+abs(a[i]-c[j]);
        xy[n+1][0]=0;
        for(int i=n;i>=1;i--)
            for(int j=1;j<=m;j++)
                xy[i][j]=min(min(xy[i+1][j-1],xy[i+1][j]),xy[i][j-1])+abs(a[i]-b[j]);
        yz[m+1][0]=0;
        for(int i=m;i>=1;i--)
            for(int j=1;j<=p;j++)
                yz[i][j]=min(min(yz[i+1][j-1],yz[i+1][j]),yz[i][j-1])+abs(b[i]-c[j]);
        for(int i=0;i<=n+1;i++)
            for(int j=0;j<=m+1;j++)
                for(int k=0;k<=p+1;k++)
                {
                    ans=min(ans,xy[i][j]+xz[i][k]+yz[j][k]);
                    ans=min(ans,xy[i][j]+xz[i][k]+yz[j+1][k]);  
                    ans=min(ans,xy[i+1][j]+xz[i][k]+yz[j][k]);  
                    ans=min(ans,xy[i][j]+xz[i][k+1]+yz[j][k]);
                    ans=min(ans,xy[i+1][j]+xz[i][k]+yz[j+1][k]);  
                    ans=min(ans,xy[i][j]+xz[i][k+1]+yz[j+1][k]);  
                    ans=min(ans,xy[i+1][j]+xz[i][k+1]+yz[j][k]);
                    ans=min(ans,xy[i+1][j]+xz[i][k+1]+yz[j+1][k]);
                }
        printf("%d\n",ans);
    }
    
    int main()
    {
        scanf("%d",&tt);
        while(tt--)
        {
            read();
            go();
        }
        return 0;
    }
    • 1

    信息

    ID
    683
    时间
    1000ms
    内存
    10MiB
    难度
    10
    标签
    递交数
    2
    已通过
    1
    上传者