题解：P8816 [CSP-J 2022] 上升点列

xu_zhihao · 2024-08-27 21:31:03 · 题解

题目理解

这道题很明显是一道 dp，但是看题解里没有我这一种有点像区间 dp 的做法。
容易看出 x_i 与 y_i 并无许多关联，不妨先将 x 排序，再考虑 y 的情况。
为避免冲突，以下的 K 为题目输入的 k。而 k 仅为变量。设 dp_{l,r} 为以 l 点为起点，r 点为终点的情况下，至少需要添加几个点。明显的，如果两点坐标的相互位置合法的，那么 dp_{l,r} 可以从 dp_{l,k} 与 dp_{k,r} 中转移而来，初始赋值为 (x_r-x_l)+(y_r-y_l)-1。初始赋值情况即为 l 点到 r 点的路径中的点都为添加的点，而转移的情况即为 l 点到 r 点的路径中的点有若干个给定的点。推得转移方程为 dp_{l,r}=\max(dp_{l,r},dp_{l,k}+dp_{k,r}),l\le k \le r。
但发现虽然求出了 dp_{l,r}，但根据定义，其仅为从 l 到 r 最少需要添加的点数。但没有满足从 l 到 r 添加了最少点数的路径点集长度，不妨设它为 sum_{l,r}，在满足 dp_{l,r} 的转移条件时，也将其转移。
根据定义，最后的答案 ans 即为 \max(ans,sum_{l,r}+(K-dp_{l,r})),1 \le l \le r \le n。
正确性。因为题目要求求出满足条件的序列的最大长度，所以就可以假设求出答案的步骤分为以下几步：
1. 求出 l 到 r 最少需添加几个点。
2. 求出满足步骤 1 的经过路径点集长度并算入贡献。
3. 将其余未添加的点算入贡献。
不难发现随着需添加的点递减，经过路径点集的长度一定不减，因为需要更多给定的点。然而也不难发现，随着需添加的点递减，步骤 3 算入的贡献一定递增。那么根据以上的分析，假设成立，这样求出的答案一定最优。
复杂度。用区间 dp 求出所有 dp_{l,r} 的复杂度为 O(n^3)。暴力求出答案的复杂度为 O(n^2)。综上所述，复杂度为 O(n^3)。

AC 代码：

#include<bits/stdc++.h>
using namespace std;
struct node{
    int x;
    int y;
};
node a[1010];
bool cmp(node l,node r){
    if(l.x!=r.x){
        return l.x<r.x;
    }
    return l.y<r.y;
}
int dp[510][510];
int sum[510][510];
int inf=1e9;
int main(){
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++){
        scanf("%d%d",&a[i].x,&a[i].y);
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            dp[i][j]=inf;//初始赋值 
        }
    } 
    sort(a+1,a+n+1,cmp);
    for(int len=2;len<=n;len++){
        for(int l=1;l<=n-len+1;l++){
            int r=l+len-1;
            if(a[r].y-a[l].y<0){
                continue;
            }
            dp[l][r]=(a[r].y-a[l].y)+(a[r].x-a[l].x)-1;
            sum[l][r]=(a[r].y-a[l].y)+(a[r].x-a[l].x)+1;

            if(len==2){
                continue;
            }

            for(int k=1;k<=n;k++){
                if(k==l || k==r){
                    continue;
                }
                if(dp[l][k]+dp[k][r]<dp[l][r]){
                    dp[l][r]=dp[l][k]+dp[k][r];
                    sum[l][r]=sum[l][k]+sum[k][r]-1;
                }
            }
        }
    }
    int mx=0;
    for(int l=1;l<=n;l++){
        for(int r=l;r<=n;r++){
            if(a[r].y-a[l].y<0 || dp[l][r]>k){
                continue;
            }
            int len=sum[l][r]+(k-dp[l][r]);
            mx=max(mx,len);
        }
    }
    printf("%d\n",mx);
    return 0; 
}

题解：P8816 [CSP-J 2022] 上升点列

题目理解

AC 代码：