CSP2022题解之 PJ T4

· · 题解

好吧，好一道 dp 题。

考虑发现，不管坐标们长啥样，最后的结果肯定是 \ge k 的（显然，如果都无法搁到一起，就直接给某个点附近加上 k 个点）

所以考虑建图。将每两个可以通过放置中间节点到达的点进行连边，然后跑最长路即可。

但是又发现，我们连出的图是一个 Dag。（很明显）

所以甚至我们可以直接记忆化搜索找出最长路。

因为是 PJ T4，所以放出考场代码：

#include<bits/stdc++.h>
using namespace std;
int n,k;
const int Maxn=610;
const int Maxk=110;
const int Maxm=2e5+10;
int head[Maxn],tot;
struct Edge{
    int to;
    int w;
    int nxt;
}E[Maxm<<1];
void addedge(int u,int v,int w)
{
    tot++;
    E[tot].to=v;
    E[tot].w=w;
    E[tot].nxt=head[u];
    head[u]=tot;
}
struct Point{
    int x,y;
}P[Maxn];
void check(int x,int y)
{
    if(P[x].x>=P[y].x && P[x].y>=P[y].y)
    {
        if(abs(P[x].x-P[y].x)+abs(P[x].y-P[y].y)-1>k) return ;
        if(abs(P[x].x-P[y].x)+abs(P[x].y-P[y].y)==1)
        {
            addedge(y,x,0);
        }else{
            addedge(y,x,abs(P[x].x-P[y].x)+abs(P[x].y-P[y].y)-1);
        }
        //cout<<y<<"->"<<x<<":"<<abs(P[x].x-P[y].x)+abs(P[x].y-P[y].y)-1<<endl;
    }
}
int dp[Maxn][Maxn];
int dfs(int u,int rk) // rk 可供用的加点数量
{
    if(dp[u][rk]!=-1) return dp[u][rk];
    int res=1;
    for(int i=head[u];i;i=E[i].nxt)
    {
        int v=E[i].to,w=E[i].w;
        if(rk>=w)
        {
            //cout<<u<<":"<<v<<endl;
            int tmp=dfs(v,rk-w)+w+1;
            res=max(res,tmp);
        }
    }
    dp[u][rk]=res;
    return res;
}
int main()
{
    //freopen("point.in","r",stdin);
    //freopen("point.out","w",stdout);
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&P[i].x,&P[i].y);
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(i==j) continue;
            check(i,j);
        }
    }
    int ans=-0x3f;
    memset(dp,-1,sizeof(dp));
    for(int i=1;i<=n;i++)
    {
        //memset(dp,-1,sizeof(dp));
        for(int j=0;j<=k;j++)
        {
            int tmp=dfs(i,j);
            tmp+=(k-j);
            //cout<<i<<":"<<j<<",tmp="<<tmp<<endl;
            ans=max(ans,tmp);
        }
    }
    printf("%d\n",ans);
    return 0;
}

时间复杂度：O(n^2k)

Q： 这题这么简单，为什么你做了 1 个小时

A： 因为我开始在进行搜索的时候，将 dp 数组重置成 -1 了……