P8816 [CSP-J 2022] 上升点列

· · 题解

0.前言

当初在考场上花了不到十分钟基本想出正解，又花了不到二十分钟把代码敲完了，然而因为自己思维方式太离谱所以最终只拿了85pts。

如今找LLZ要回了自己的考场代码，稍作修改，于是A了。

不得不说的是自己的思路确实不够完善，因此也并没有可惜这15分的意思（反正1=也拿到了），倒是长了个教训。

如今把我写这道题的全过程分享在自己的blog里，也算是总结了。

那我们就开始吧。

1.在考场上

拿到这题以后一眼最长上升子序列，看了一眼数据范围觉得很水，于是想了个简单的思路。

只是最长上升子序列的做法而已，给点排一下序然后直接dp即可。

实在是不知道如何仔细讲解这个思路，主要是真要细讲的话可能也就说说最长上升子序列这种东西，实在是没什么必要。

但是我在面对“最后不一定把所有点加完，所以还需要把没加的点加上”时，脑子抽了一下：我选择了先比较dp数组中的最大答案，最后再找这些最大值中能加的最多的点数量。

但是事实上，在某些情况下，dp数组中的某个非最大值在加上没加的点之后就是最优解，而我恰好忽略了这一点。

我真是个弱智。

顺便把考场代码贴一下吧。

#include<bits/stdc++.h>
using namespace std;
int n,k,dp[501][101],ans=0,orz=1000;
struct dots{
    int x,y;
    bool operator < (const dots &zgc)const{
        if (x!=zgc.x){
            return x<zgc.x;
        }
        return y<zgc.y;
    }
}a[501];
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",&a[i].x,&a[i].y);
        dp[i][0]=1;
    }
    sort(a+1,a+1+n);
    for (int i=2;i<=n;i++){
        for (int j=1;j<i;j++){
            if (a[i].x<a[j].x||a[i].y<a[j].y){
                continue;
            }
            int kk=a[i].x-a[j].x+a[i].y-a[j].y-1;
            for (int add=kk;add<=k;add++){
                dp[i][add]=max(dp[i][add],dp[j][add-kk]+1+kk);
            }
        }
    }
    for (int i=1;i<=n;i++){
        for (int j=0;j<=k;j++){
            ans=max(ans,dp[i][j]);
        }
    }
    for (int i=1;i<=n;i++){
        for (int j=0;j<=k;j++){
            if (ans==dp[i][j]){
                orz=min(orz,j);
            }
        }
    }
    printf("%d",ans+k-orz);
    return 0;
}

2.呼之欲出的正解

只需要修改一下考场代码即可。

将最后的找最大值的部分改了一下，改成直接找答案。

于是AC。

#include<bits/stdc++.h>
using namespace std;
int n,k,dp[501][101],ans=0;
struct dots{
    int x,y;
    bool operator < (const dots &zgc)const{
        if (x!=zgc.x){
            return x<zgc.x;
        }
        return y<zgc.y;
    }
}a[501];
int main()
{
    scanf("%d%d",&n,&k);
    for (int i=1;i<=n;i++){
        scanf("%d%d",&a[i].x,&a[i].y);
        dp[i][0]=1;
    }
    sort(a+1,a+1+n);
    for (int i=2;i<=n;i++){
        for (int j=1;j<i;j++){
            if (a[i].x<a[j].x||a[i].y<a[j].y){
                continue;
            }
            int kk=a[i].x-a[j].x+a[i].y-a[j].y-1;
            for (int add=kk;add<=k;add++){
                dp[i][add]=max(dp[i][add],dp[j][add-kk]+1+kk);
            }
        }
    }
    for (int i=1;i<=n;i++){
        for (int j=0;j<=k;j++){
            ans=max(ans,dp[i][j]+k-j);
        }
    }
    printf("%d",ans);
    return 0;
}

撒花，顺便再次感叹我是弱智。