CSP-J2022T4

Bot_wxt1221 · 2022-11-05 15:20:47 · 题解

题目传送门

简化题意：二维平面上有 n 个点，还可以再添加 k 个点，坐标要求是整数，选取一个点序列使得序列中每个点个横纵坐标非严格单调递增且满足 x_{i+1}-x_{i}=1、y_{i+1}=y_{i} 或 y_{i+1}-y_{i}=1、x_{i+1}=x_{i}，序列最长是多少。

错误思路：按照坐标排序选取其中一段是不对的，具体可以手推样例，根本不可能从 (3,6) 跑到 (5,3)，但是按照这样的思路一定是连起来的。

正解：在对着坐标轴发呆后，突然发现可以用中转的思想，一看 0\leq n \leq 500，Floyd 走一波，初始化为两点的曼哈顿距离减 1，跑一遍 Floyd 跑出两点连通需要加的最少边。

细节：可能两个连接后还可以加点，直接无脑加在最后，所以统计时要加上 k-map_{i,j}。

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
long long read(){
    char temp=getchar();
    long long f=1,x=0;
    while('0'>temp||temp>'9'){
        (temp=='-')?(f=-1):0;
        temp=getchar();
    }
    while('0'<=temp&&temp<='9'){
        x=(x<<3)+(x<<1)+(temp^'0');
        temp=getchar();
    }
    return f*x;
}
long long x[505];
long long y[505];
long long map[505][505];
int mian(){
//  freopen("point.in","r",stdin);
//  freopen("point.out","w",stdout);
    int n=read();
    int k=read();
    for(int i=1;i<=n;i++){
        x[i]=read();
        y[i]=read();
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i==j){
                map[i][j]=0;
            }else if(x[j]>=x[i]&&y[j]>=y[i])
                map[i][j]=abs(x[i]-x[j])+abs(y[i]-y[j])-1;
            else{
                map[i][j]=0x3f3f3f3f3f3f3f3fll;
            }
        }
    }
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                map[i][j]=min(map[i][j],map[i][k]+map[k][j]);
            }
        } 
    }
    long long ans=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(map[i][j]<=k){
                ans=max(ans,abs(x[i]-x[j])+abs(y[i]-y[j])+(k-map[i][j])+1);
            }
        }
    }
    printf("%lld",ans);
    return 0;
}

欢迎到博客看其他题解。

UPD：感谢机房巨巨巨巨巨佬 gyc 指正曼哈顿距离和欧几里得距离的区别。