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

20分采用暴力搜索方法。使用深度优先搜索DFS进行遍历。对于每个点有两种选择将其加入序列或不加入序列。当遍历到第n个点时对生成的序列进行合法性判断。判断序列是否合法需满足两个条件序列单调不减且相邻两点之间的欧几里得距离为1即一个点要么在另一个点的正上方要么在正下方。如果两点之间出现单调递减则序列不合法如果两点之间需要补充的点数超过k同样不合法。#includebits/stdc.husingnamespacestd;intn,k;vectorpairint,intp;intmaxn0;voidcheck(constvectorintc){if(c.empty())return;vectorpairint,intcur;for(intidx:c){cur.push_back(p[idx]);}sort(cur.begin(),cur.end());//单调性的检查booloktrue;for(inti1;icur.size();i){if(cur[i].firstcur[i-1].first||cur[i].secondcur[i-1].second){okfalse;break;}}if(!ok)return;//计算需要添加的点数 d(x2-x1)(y2-y1)intcost0;for(inti1;icur.size();i){intdxcur[i].first-cur[i-1].first;intdycur[i].second-cur[i-1].second;cost(dxdy-1);//需要补的点数}if(costk){maxnmax(maxn,(int)c.size());}}voiddfs(intidx,vectorintc){if(idxn){check(c);return;}dfs(idx1,c);c.push_back(idx);dfs(idx1,c);c.pop_back();}intmain(){cinnk;for(inti0;in;i){intx,y;cinxy;p.push_back({x,y});}vectorintc;dfs(0,c);coutmaxnk;return0;}100分法一采用暴力搜索结合记忆化优化。由于DFS本身没有明显的记忆化点因此将记忆化策略应用在check函数中。我们知道从一个点出发可以走很多条路有一些路是有重叠的。所以可以记录每条路的子路的长度到时候重叠部分直接用即可。#includebits/stdc.husingnamespacestd;intn,k;vectorpairint,intp;intmemo[505][505];intmaxn0;intdfs(inti,intused)//used是之前补的点数{if(memo[i][used]!-1)returnmemo[i][used];intbest1;for(intji1;jn;j){if(p[j].secondp[i].second)continue;//递减直接跳过intdxp[j].first-p[i].first;intdyp[j].second-p[i].second;intneeddxdy-1;if(usedneedk){bestmax(best,dfs(j,usedneed1);//找最长序列}}returnmemo[i][used]best;//记忆化}intmain(){cinnk;for(inti0;in;i){intx,y;cinxy;p.push_back({x,y});}sort(p.begin(),p.end());memset(memo,-1,sizeof(memo));for(inti0;in;i){maxnmax(maxn,dfs(i,0));}coutmaxnk;return0;}100分法二暴力有一定风险我们可以想想用dp。实际上就是把记忆化数组变成dp数组就行了只不过dp[i][0]要赋初值为1。策略改在某个点往后探索为以该点结尾中间某点开始到这里。但是used需要我们自己枚举也充当dp[x][y]中的y。就是从某点此前花费used个点下一个点接该点不算补的点的长度装进dp数组。#includebits/stdc.husingnamespacestd;intn,k;vectorpairint,intp;intdp[505][505];intmaxn0;intmain(){cinnk;for(inti0;in;i){intx,y;cinxy;p.push_back({x,y});}sort(p.begin(),p.end());for(inti0;in;i){dp[i][0]1;for(intj0;ji;j){if(p[i].secondp[j].second)continue;intdxp[i].first-p[j].first;intdyp[i].second-p[j].second;intneeddxdy-1;for(intused0;usedneedk;used){dp[i][usedneed]max(dp[i][usedneed],dp[j][used]1);}}}for(inti0;in;i){for(intused0;usedk;used){maxnmax(dp[i][used],maxn);}}coutmaxnk;return0;}