洛谷P8816 [CSP-J 2022] 上升点列一题的题解

20分

采用暴力搜索方法。使用深度优先搜索（DFS）进行遍历。对于每个点，有两种选择：将其加入序列或不加入序列。当遍历到第n个点时，对生成的序列进行合法性判断。

判断序列是否合法需满足两个条件：序列单调不减，且相邻两点之间的欧几里得距离为1（即一个点要么在另一个点的正上方，要么在正下方）。如果两点之间出现单调递减，则序列不合法；如果两点之间需要补充的点数超过k，同样不合法。

#include<bits/stdc++.h>usingnamespacestd;intn,k;vector<pair<int,int>>p;intmaxn=0;voidcheck(constvector<int>&c){if(c.empty())return;vector<pair<int,int>>cur;for(intidx:c){cur.push_back(p[idx]);}sort(cur.begin(),cur.end());//单调性的检查boolok=true;for(inti=1;i<cur.size();i++){if(cur[i].first<cur[i-1].first||cur[i].second<cur[i-1].second){ok=false;break;}}if(!ok)return;//计算需要添加的点数 d=(x2-x1)+(y2-y1)intcost=0;for(inti=1;i<cur.size();i++){intdx=cur[i].first-cur[i-1].first;intdy=cur[i].second-cur[i-1].second;cost+=(dx+dy-1);//需要补的点数}if(cost<=k){maxn=max(maxn,(int)c.size());}}voiddfs(intidx,vector<int>&c){if(idx==n){check(c);return;}dfs(idx+1,c);c.push_back(idx);dfs(idx+1,c);c.pop_back();}intmain(){cin>>n>>k;for(inti=0;i<n;i++){intx,y;cin>>x>>y;p.push_back({x,y});}vector<int>c;dfs(0,c);cout<<maxn+k;return0;}

100分法一

采用暴力搜索结合记忆化优化。由于DFS本身没有明显的记忆化点，因此将记忆化策略应用在check函数中。
我们知道，从一个点出发可以走很多条路，有一些路是有重叠的。所以可以记录每条路的子路的长度，到时候重叠部分直接用即可。

#include<bits/stdc++.h>usingnamespacestd;intn,k;vector<pair<int,int>>p;intmemo[505][505];intmaxn=0;intdfs(inti,intused)//used是之前补的点数{if(memo[i][used]!=-1)returnmemo[i][used];intbest=1;for(intj=i+1;j<n;j++){if(p[j].second<p[i].second)continue;//递减直接跳过intdx=p[j].first-p[i].first;intdy=p[j].second-p[i].second;intneed=dx+dy-1;if(used+need<=k){best=max(best,dfs(j,used+need+1);//找最长序列}}returnmemo[i][used]=best;//记忆化}intmain(){cin>>n>>k;for(inti=0;i<n;i++){intx,y;cin>>x>>y;p.push_back({x,y});}sort(p.begin(),p.end());memset(memo,-1,sizeof(memo));for(inti=0;i<n;i++){maxn=max(maxn,dfs(i,0));}cout<<maxn+k;return0;}

100分法二

暴力有一定风险，我们可以想想用dp。
实际上就是把记忆化数组变成dp数组就行了，只不过dp[i][0]要赋初值为1。策略：改在某个点往后探索为以该点结尾，中间某点开始到这里。但是used需要我们自己枚举，也充当dp[x][y]中的y。就是：从某点，此前花费used个点，下一个点接该点（不算补的点）的长度装进dp数组。

#include<bits/stdc++.h>usingnamespacestd;intn,k;vector<pair<int,int>>p;intdp[505][505];intmaxn=0;intmain(){cin>>n>>k;for(inti=0;i<n;i++){intx,y;cin>>x>>y;p.push_back({x,y});}sort(p.begin(),p.end());for(inti=0;i<n;i++){dp[i][0]=1;for(intj=0;j<i;j++){if(p[i].second<p[j].second)continue;intdx=p[i].first-p[j].first;intdy=p[i].second-p[j].second;intneed=dx+dy-1;for(intused=0;used+need<=k;used++){dp[i][used+need]=max(dp[i][used+need],dp[j][used]+1);}}}for(inti=0;i<n;i++){for(intused=0;used<=k;used++){maxn=max(dp[i][used],maxn);}}cout<<maxn+k;return0;}