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

[题目传送门](https://www.luogu.com.cn/problem/P8816)

这道题很有意思，做法还蛮多的。

## 深搜（无优化）

我们可以先回归朴素，直接按题意去对每一个起点深搜，找到所有合法的点列路径。

```cpp
#include<bits/stdc++.h>
using namespace std;
#define N 505
int n,p,ans;
bitset<N>f;//类似bool数组，在O2优化下效率比bool数组更高
struct pt{
    int x,y;
}a[N];
bool cmp(pt x,pt y){//判断是否递增
    if(x.x>y.x||x.y>y.y)return 0;
    return 1;
}
void dfs(int k,int lp,int len){
    for(int i=1;i<=n;i++){
        if(!f[i]&&k!=i&&cmp(a[k],a[i])){//没选且不是自己且是递增的
            int dis=a[i].x-a[k].x+a[i].y-a[k].y-1;
            //两个点如果要直达需要放的点数
            if(dis>lp)continue;
            f[i]=1;//标记已经选过
            dfs(i,lp-dis,len+dis+1);//继续dfs
            f[i]=0;//回溯
        }
    }
    ans=max(ans,len+lp);//当前数列长度加剩下没放的点数
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>p;
    for(int i=1;i<=n;i++)
        cin>>a[i].x>>a[i].y;
    for(int i=1;i<=n;i++)
        dfs(i,p,1);
    cout<<ans;
    return 0;
}
```

代码很精简，分数自然也不会高到哪里去。

最劣时间复杂度：$O(n\times 2^n)$。

用时：$30.11\text{s}$。

内存：$0.76\text{MB}$。

分数：$35$。

## 深搜（剪枝）

观察之前的朴素深搜，发现每次搜都要从 $n$ 个点中全部判断一遍，有些不能和当前点组成上升点列的点也被判断了，一轮判断可能效率降低的不明显，但是多轮判断就会很慢了。

于是我们可以对每个点预处理出能与当前点组成上升点列的点，然后直接深搜就行了。

```cpp
#include<bits/stdc++.h>
using namespace std;
#define N 505
#define dist(i,k) a[i].x-a[k].x+a[i].y-a[k].y-1//曼哈顿距离-1
int n,p,ans;
bitset<N>f;//类似bool数组，在O2优化下效率比bool数组更高
struct pt{
    int x,y;
    vector<int>e;//存储能组成上升点列的点
}a[N];
bool cmp(pt x,pt y){//判断是否递增
    if(x.x>y.x||x.y>y.y)return 0;
    return 1;
}
void dfs(int k,int lp,int len){
    f[k]=1;//选择
    for(int i:a[k].e){//逐点遍历
        if(!f[i]&&k!=i&&cmp(a[k],a[i])){//没选且不是自己且是递增的
            int dis=dist(i,k);
            //两个点如果要直达需要放的点数
            if(dis>lp)continue;
            dfs(i,lp-dis,len+dis+1);//继续dfs
        }
    }
    ans=max(ans,len+lp);//当前数列长度加剩下没放的点数
    f[k]=0;//回溯
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>p;
    for(int i=1;i<=n;i++)
        cin>>a[i].x>>a[i].y;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i==j||a[i].x>a[j].x||a[i].y>a[j].y||dist(j,i)>p)continue;
            //如果是同一个点或者无法组成上升点列或距离大于k就跳过
            a[i].e.push_back(j);
        }
    }
    for(int i=1;i<=n;i++)
        dfs(i,p,1);
    cout<<ans;
    return 0;
}
```

实质上就是剪了一些枝，大体还是没什么变化的。

最劣时间复杂度：$O(n\times 2^n)$

用时：$27.31\text{s}$。

内存：$0.84\text{MB}$。

分数：$40$。

## 动态规划（最长不下降子序列）

我们可以发现，当 $k=0$ 时，问题就转化为了求最长不下降子序列的问题，另外，我们可以在直接给答案加上 $k$。

如果有的数据点答案是在其最长不下降子序列后面添上 $k$ 个点，便可以拿到这个点的分。

```cpp
#include<bits/stdc++.h>
using namespace std;
#define N 505
int n,p,ans,dp[N];
struct pt{
    int x,y;
}a[N];
bool cmp(pt x,pt y){
    if(x.x!=y.x)return x.x<y.x;
    return x.y<y.y;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>p;
    for(int i=1;i<=n;i++){
        cin>>a[i].x>>a[i].y;
        dp[i]=1;//初始化为1
    }
    sort(a+1,a+1+n,cmp);//按坐标排序保证dp顺序
    for(int i=1;i<=n;i++){
        for(int j=1;j<n;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);
        }
    }
    for(int i=1;i<=n;i++)
        ans=max(ans,dp[i]);
    cout<<ans+p;
    return 0;
}
```

改下判断递增的部分然后套模板即可，代码非常精简。

最劣时间复杂度：$O(n^2)$。

用时：$0.147\text{s}$。

内存：$0.86\text{MB}$。

分数：$45$。

## 广搜

我们观察数据范围，可以发现有很多的数据点满足 $x_{max},y_{max}\le100$，于是我们可以用二维数组存下来然后对每个点进行广搜。

搜的方向只有右与上方，满足题意，当走到没点的位置时减去剩余可放置点数，否则不减，相当于点权有两种，所以可以当 $01\text{BFS}$ 问题来做，故我们选择使用双端队列 `deque`。

```cpp
#include<bits/stdc++.h>
using namespace std;
#define N 505
int n,p,ans,dx[]={1,0},dy[]={0,1};
int x[N],y[N];
bool mp[105][105],v[105][105];
void bfs(int x,int y){
    memset(v,0,sizeof(v));//初始化
    deque<int>qx,qy,ql,qs;
    v[x][y]=1;
    qx.push_back(x);qy.push_back(y);
    ql.push_back(p);qs.push_back(1);
    while(!qx.empty()){
        int xx=qx.front(),yy=qy.front();
        int lp=ql.front(),st=qs.front();
        ans=max(ans,st+lp);//路径长度+剩余点
        qx.pop_front();qy.pop_front();
        ql.pop_front();qs.pop_front();
        for(int i=0;i<2;i++){
            int tx=xx+dx[i],ty=yy+dy[i];
            if(tx>100||ty>100||v[tx][ty])continue;
            v[tx][ty]=1;
            if(mp[tx][ty]){//位置上有点，加入到队头
                qx.push_front(tx);qy.push_front(ty);
                ql.push_front(lp);qs.push_front(st+1);
            }
            else{//位置上没点，剩余点减去1，并加入到队尾
                if(lp==0)continue;//没点能用了就跳过
                qx.push_back(tx);qy.push_back(ty);
                ql.push_back(lp-1);qs.push_back(st+1);
            }
        }
    }
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>p;
    for(int i=1;i<=n;i++){
        cin>>x[i]>>y[i];
        mp[x[i]][y[i]]=1;
    }
    for(int i=1;i<=n;i++)
        bfs(x[i],y[i]);//对每个起点都BFS
    cout<<ans;
    return 0;
}
```

双端队列 $\text{BFS}$ 的小应用，实现也不是很难。

最劣时间复杂度：$O(nx_{max}y_{max})$。

用时：$0.199\text{s}$。

内存：$0.78\text{MB}$。

分数：$60$。

## 动态规划（对坐标递推）

我们令 $dp_{x,y}$ 为走到 $(x,y)$ 且以 $(x,y)$ 结尾的最长上升点列，$cost_{x,y}$ 为最长上升点列中额外放置的点的数量。

不难推出，当 $(x,y)$ 上已经有点时，$dp_{x,y}=max(dp_{x,y-1},dp_{x,y-1})+1,cost_{x,y}$ 即为 $(x,y-1)$ 与 $(x-1,y)$ 中 $dp$ 值较大的一个点的 $cost$ 值，如果他们的 $dp$ 值相等，则选择 $cost$ 值较小的一个点进行转移。

当 $(x,y)$ 上没有点时，仍然有 $dp_{x,y}=max(dp_{x,y-1},dp_{x,y-1})+1$，但约束条件是这两个点的 $cost$ 值要小于 $k$，$cost_{x,y}$ 即为 $(x,y-1)$ 与 $(x-1,y)$ 两个点中合法的点构成的点集中 $dp$ 值较大的点的 $cost$ 值加上 $1$。

```cpp
#include<bits/stdc++.h>
using namespace std;
#define N 505
int n,p,ans,x[N],y[N];
int cost[105][105],dp[105][105];
bool mp[105][105];
inline void upd1(int tx,int ty,int add){//从(x-1,y)转移
    //当(tx,ty)没点时，add为1，代表多消耗一个点
    dp[tx][ty]=dp[tx-1][ty]+1;
    cost[tx][ty]=cost[tx-1][ty]+add;
}
inline void upd2(int tx,int ty,int add){//从(x,y-1)转移
    dp[tx][ty]=dp[tx][ty-1]+1;
    cost[tx][ty]=cost[tx][ty-1]+add;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>p;
    for(int i=1;i<=n;i++){
        cin>>x[i]>>y[i];
        mp[x[i]][y[i]]=1;
    }
    for(int i=1;i<=n;i++){//对每个点都dp
        memset(cost,0,sizeof(cost));
        memset(dp,0,sizeof(dp));//初始化
        for(int tx=x[i];tx<=100;tx++){
            for(int ty=y[i];ty<=100;ty++){
                if(mp[tx][ty]){//有点
                    if(dp[tx-1][ty]>dp[tx][ty-1])
                        upd1(tx,ty,0);
                    else if(dp[tx-1][ty]<dp[tx][ty-1])
                        upd2(tx,ty,0);
                    else
                        if(cost[tx-1][ty]<cost[tx][ty-1])
                            upd1(tx,ty,0);
                        else
                            upd2(tx,ty,0);
                }
                else{//没有点
                    if(cost[tx-1][ty]<p&&cost[tx][ty-1]<p){
                        if(dp[tx-1][ty]>dp[tx][ty-1])
                            upd1(tx,ty,1);
                        else if(dp[tx-1][ty]<dp[tx][ty-1])
                            upd2(tx,ty,1);
                        else
                            if(cost[tx-1][ty]<cost[tx][ty-1])
                                upd1(tx,ty,1);
                            else
                                upd2(tx,ty,1);
                    }
                    else{
                        if(cost[tx-1][ty]<p)
                            upd1(tx,ty,1);
                        if(cost[tx][ty-1]<p)
                            upd2(tx,ty,1);
                        //若都没有剩余可放置的点了干脆不转移，此时的dp[x][y]也满足定义。
                    }
                }
                ans=max(ans,dp[tx][ty]+p-cost[tx][ty]);//路径长度+剩余点
            }
        }
    }
    cout<<ans;
    return 0;
}
```

本质上就是从 $\text{BFS}$ 改过来的，因为只有两个方向，所以很容易实现无后效性的动态规划，不过细节相对较多，但是效率也更高。

最劣时间复杂度：$O(nx_{max}y_{max})$。

用时：$0.151\text{s}$。

内存：$0.79\text{MB}$。

分数：$60$。

## 图论最短路（Dijkstra单源最短路）

我们考虑建图，满足组成上升点列的两个点之间连一条边，边权为其曼哈顿距离减 $1$，即要使这两点直接连通要放的点数。

于是问题就转化成了求点到点之间最少要放的点数，放的越少，能直接放到后面的点就越多，答案也就越优。

```cpp
#include<bits/stdc++.h>
using namespace std;
#define N 505
#define pr pair<int,int>
#define dist first
#define id second
#define gdis(i,k) (a[i].x-a[k].x+a[i].y-a[k].y-1)//曼哈顿距离-1
int n,k,ans,dis[N];
bitset<N>f;//类似bool数组，在O2优化下效率比bool数组更高
struct edge{//边结构体
    int t,w;
    edge(int a,int b){t=a,w=b;}
};
struct pt{
    int x,y;
}a[N];
vector<edge>e[N];
void dijkstra(int s){//单源最短路算法
    for(int i=1;i<=n;i++)dis[i]=INT_MAX;
    dis[s]=0;
    f.reset();
    priority_queue<pr,vector<pr>,greater<pr>>q;
    q.push({dis[s],s});
    while(!q.empty()){
        pr u=q.top();
        q.pop();
        if(f[u.id])continue;
        f[u.id]=1;
        for(edge x:e[u.id]){
            if(u.dist+x.w<dis[x.t]){
                dis[x.t]=u.dist+x.w;
                q.push({dis[x.t],x.t});
            }
        }
    }
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>k;
    for(int i=1;i<=n;i++)
        cin>>a[i].x>>a[i].y;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i==j||a[i].x>a[j].x||a[i].y>a[j].y||gdis(j,i)>k)continue;//不符合要求跳过
            e[i].push_back(edge(j,gdis(j,i)));//建边
        }
    }
    for(int i=1;i<=n;i++){
        dijkstra(i);
        for(int j=1;j<=n;j++){
            if(dis[j]>k)continue;//最少要放的点数大于k跳过
            ans=max(ans,gdis(j,i)+1+k-dis[j]+1);//路径长度加剩余点数
        }
    }
    cout<<ans;
    return 0;
}
```

建完边直接套 $\text{Dijkstra}$ 模板即可，同理其他复杂度较低的单源最短路算法也能做。

最劣时间复杂度：远远小于 $O(n^3\log n^2)$。

复杂度证明：$k\le100$，所以最多只能给曼哈顿距离小于等于 $101$ 的点对连边，而部分数据满足 $x_{max},y_{max}\le 10^9$，按照正常的造数据的思维绝对会把点的位置造的很分散，所以一个点的出边会远远小于 $n$，当 $x_{max},y_{max}\le 100$ 时，才会有更接近 $O(n^3\log n^2)$ 的复杂度，不过离吃满还有相当一段距离，参考[评测记录](https://www.luogu.com.cn/record/124286664)，可以发现该代码在 $x_{max},y_{max}\le 100$ 的数据下跑得比 $x_{max},y_{max}\le 10^9$ 慢不少。

用时：$2.00\text{s}$。

内存：$1.60\text{MB}$。

分数：$100$。

## 图论最短路（Floyd全源最短路&动态规划）

观察数据范围，节点数最多只有 $500$，所以我们考虑用动态规划实现的全源最短路算法，$\text{Floyd}$。

```cpp
#include<bits/stdc++.h>
using namespace std;
#define N 505
#define gdis(i,k) (a[i].x-a[k].x+a[i].y-a[k].y-1)//曼哈顿距离-1
int n,k,ans,f[N][N];
struct pt{
	int x,y;
}a[N];
void floyd(){//全源最短路算法
	for(int k=1;k<=n;k++)
		for(int i=1;i<=n;i++)
			if(f[i][k]!=(INT_MAX>>1))//剪枝，判断i能否到k，不然提前退出
            for(int j=1;j<=n;j++)
					f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>k;
	for(int i=1;i<=n;i++)
		cin>>a[i].x>>a[i].y;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			f[i][j]=i==j?0:INT_MAX>>1;//初始化
			if(i==j||a[i].x>a[j].x||a[i].y>a[j].y||gdis(j,i)>k)continue;//不符合要求跳过
			f[i][j]=gdis(j,i);//建边
		}
	}
	floyd();
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			if(f[i][j]<=k)ans=max(ans,gdis(j,i)+1+k-f[i][j]+1);
	cout<<ans;
	return 0;
}
```

建完边直接套 $\text{Floyd}$ 模板即可，代码异常精简。

最劣时间复杂度：$O(n^3)$。

用时：$0.453\text{s}$。

内存：$1.43\text{MB}$。

分数：$100$。

## 动态规划（对点递推）

我们令 $dp_{i,p}$ 为以第 $i$ 个点为终点，剩余 $p$ 个可放置的点时最长的上升点列，$dis_{i,j}$ 为第 $i$ 与第 $j$ 个点的曼哈顿距离减 $1$。

于是 $dp_{i,p}=max\{dp_{j,p-dis_{i,j}}+dis_{i,j}+1\}(j<i,dis_{i,j}\le p)$。

```cpp
#include<bits/stdc++.h>
using namespace std;
#define N 505
#define K 105
#define dist(i,k) (a[i].x-a[k].x+a[i].y-a[k].y-1)//曼哈顿距离-1
int n,k,ans,dp[N][K];
struct pt{
    int x,y;
}a[N];
bool cmp(pt x,pt y){
    if(x.x!=y.x)return x.x<y.x;
    return x.y<y.y;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>k;
    for(int i=1;i<=n;i++)
        cin>>a[i].x>>a[i].y;
    sort(a+1,a+1+n,cmp);//按坐标排序，保证DP顺序正确
    for(int p=0;p<=k;p++)
        for(int i=1;i<=n;i++)
            dp[i][p]=1;//初始化为1
    for(int p=0;p<=k;p++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<i;j++){
                if(a[j].y>a[i].y||dist(i,j)>p)continue;//判断合法
                dp[i][p]=max(dp[i][p],dp[j][p-dist(i,j)]+dist(i,j)+1);
                //状态转移
            }
        }
    }
    for(int p=0;p<=k;p++)
        for(int i=1;i<=n;i++)
            ans=max(ans,dp[i][p]+k-p);//路径长度+剩余点数
    cout<<ans;
    return 0;
}
```

代码出奇的精简，但是有些细节，难度基本都在推式子上面。

最劣时间复杂度：$O(kn^2)$。

用时：$0.375\text{s}$。

内存：$0.88\text{MB}$。

分数：$100$。

正在渲染内容...