P8816 [CSP-J 2022] 上升点列
Liujy_bc
·
·
题解
说实话这道题最为最后一题稍微简单了，这篇题解将从部分分到正解把我的赛时想法展现出来。
1.$ $k=0
看完题面，这道题好像最长上升子序列的模板题哎！那我们肯定先把所有的点按坐标从左到右再从下至上排序。接下来应该怎么办呢？
要是没有添加点的操作就可以直接 O(n^2) 做了呢。看一看有 45 分 k=0 的分耶！于是我们设 dp_i 表示以第排序后的第 i 个点的最大长度。
显然 dp_i=\max_{j=1}^i{dp_j+1}，其中 j 一定要判断可以到达 i 才可以转移。
2.$ $x_i,y_i\le100
然后我又看向了 x_i,y_i\le100 的点，这两档分加起来就有 75 了呢！于是我们设 f_{i,j,l} 表示以坐标 (i,j) 作为最后一个点，且一共添加了 l 个点的最大长度。
如果 (i,j) 本身存在的话，f_{i,j,l}=\max(f_{i-1,j,l}+1,f_{i,j-1,l}+1)。 如果 (i,j) 不在给定的点中，那么 f_{i,j,l}=\max(f_{i-1,j,l-1}+1,f_{i,j-1,l-1}+1)。
基于第一部分，我们可以之间枚举当前点从哪个点转移过来，显然两个点之间需要添加的点的个数是确定的，我们设 $c_{i,l}$ 表示以第 $i$ 个点作为结尾，且添加了 $l$ 个点的最大长度。显然 $c_{i,l}=\max_{j=1}^i{c_{j,l-d}+d+1}$，其中 $j$ 一定要判断可以到达 $i$ 才可以转移，$d$ 表示点 $j$ 到 $i$ 之间需要添加的点数，$d=x_i-x_j+y_i-y_j-1$。注意最后一个点不一定是已经存在的点，所以还要枚举一下把剩下还可以添加的点加在点 $i$ 后面的长度。
最后附上赛时代码。其实只需要 $work3$ 这个函数就可以啦，另外两个是部分分。
```cpp
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int n,k,ans,dp[105],f[105][105][105],c[105][105],mx;bool p[105][105];
struct node{
int x,y;
bool operator < (node b)const{
if(x==b.x)return y<b.y;
return x<b.x;
}
}a[505];
void work1(){
for(int i=1;i<=n;i++){
dp[i]=1;
for(int j=1;j<i;j++)
if(a[i].x-a[j].x==1&&a[i].y==a[j].y||(a[i].y-a[j].y==1&&a[i].x==a[j].x))dp[i]=max(dp[i],dp[j]+1);
ans=max(ans,dp[i]);
}
}
void work2(){
for(int i=1;i<=n;i++)p[a[i].x][a[i].y]=1;
for(int i=1;i<=100;i++)
for(int j=1;j<=100;j++){
if(p[i][j]){
for(int l=0;l<=k;l++){
f[i][j][l]=max(f[i-1][j][l]+1,f[i][j][l]);
f[i][j][l]=max(f[i][j-1][l]+1,f[i][j][l]);
ans=max(ans,f[i][j][l]);
}
}else{
for(int l=1;l<=k;l++){
f[i][j][l]=max(f[i-1][j][l-1]+1,f[i][j][l]);
f[i][j][l]=max(f[i][j-1][l-1]+1,f[i][j][l]);
ans=max(ans,f[i][j][l]);
}
}
}
}
void work3(){
for(int i=1;i<=n;i++){
c[i][0]=1;
for(int j=i-1;j>=1;j--){
if(a[j].x>a[i].x||a[j].y>a[i].y)continue ;
int x=a[i].x-a[j].x+a[i].y-a[j].y-1;
for(int l=x;l<=k;l++)c[i][l]=max(c[j][l-x]+x+1,c[i][l]);
}
for(int l=0;l<=k;l++)ans=max(c[i][l],ans);
}
for(int i=1;i<=n;i++)
for(int j=0;j<=k;j++)
ans=max(ans,c[i][j]+(k-j));
}
int main(){
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++){
scanf("%d%d",&a[i].x,&a[i].y);
mx=max(a[i].x,a[i].y);
}
sort(a+1,a+n+1);
if(k==0)work1();
else if(mx<=100)work2();
else work3();
printf("%d",ans);
return 0;
}
```