题目描述在二维平面上给定 n 个整数点允许自由添加最多 k 个整数点。选出若干点组成序列相邻两点欧几里得距离等于 1只能向右(1,0)或者向上(0,1)横纵坐标均单调不减求序列的最大长度。序列的长度 原始选出来的点数量 我们自由添加的点数量。关键点理解序列只能向右、向上走所以整个序列的点满足 x 不下降、y 不下降。已有两点j(x1,y1)必须满足x2x1,y2y1。两点欧几里得距离d(x2-x1)(y2-y1)想要把两点连成连续路径中间需要补dxdy-1个新增点。没有用完的新增点可以全部接在序列的末尾继续向右 / 向上延伸每一个新增点都贡献序列长度。20分暴力DFS思路:枚举原始点的全部子集子集数量2^n。把子集内点排序检查是否满足(x,y)单调不减计算把这些点串起来一共需要多少新增点 cost如果costk代表这个子集可行。总长度 子集大小(k-cost)。#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());//单调性的检查for(inti1;icur.size();i){if(cur[i].firstcur[i-1].first||cur[i].secondcur[i-1].second){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(inti1;in;i){intx,y;cinxy;p.push_back({x,y});}vectorintc;dfs(0,c);coutmaxnk;return0;}AC解一记忆化dfs思路点先排序按 x 升序x 相同 y 升序。j i 保证p[j].xp[i].x。dfs(i,used)当前以第 i 号原始点作为序列结尾已经消耗used个新增点能选出最多多少个原始点。从 i 向后枚举每一个j(ji)满足yjyi计算连接 i 到 j 需要补充的点needdxdy-1。如果总消耗 (usedneed \le k)就可以跳去 jdfs(j,usedneed)1原始点数目 1。memo[i][used]记忆化缓存避免重复递归计算。初始每一个点作为起点初始消耗used0调用dfs(i,0)得到该起点最多原始点数量。输出写的 maxnk。#includebits/stdc.husingnamespacestd;intn,k;vectorpairint,intp;intmemo[505][505];intmaxn0;intdfs(inti,intused){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,usedneed)1);}}returnmemo[i][used]best;}intmain(){cinnk;for(inti0;in;i){intx,y;cinxy;p.push_back({x,y});}sort(p.begin(),p.end());vectorintc;memset(memo,-1,sizeof(memo));for(inti0;in;i){maxnmax(maxn,dfs(i,0));}coutmaxnk;return0;}AC解二DPDP定义dp[i][used]以第 i 个原始点作为序列最后一个点连接过程已经消耗used个新增点序列中原始点的数量。状态转移j 在 i 的前面满足p[i].y p[j].y。两点之间连接需要新增点need (p[i].x-p[j].x)(p[i].y-p[j].y)-1枚举之前已经消耗的新增点数目used当usedneed k代表资源够用dp[i][usedneed]max(dp[i][usedneed],dp[j][used]1)含义原来以 j 结尾消耗used个点连上 i 之后多消耗need个点原始点数量 1。#includebits/stdc.husingnamespacestd;constintMAXN505;constintMAXK105;intn,k;vectorpairint,intp;intdp[MAXN][MAXK];intmain(){cinnk;for(inti0;in;i){intx,y;cinxy;p.emplace_back(x,y);}sort(p.begin(),p.end());memset(dp,0,sizeof(dp));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){if(dp[j][used]0)continue;dp[i][usedneed]max(dp[i][usedneed],dp[j][used]1);}}}intans0;for(inti0;in;i){for(intused0;usedk;used){if(dp[i][used]0)continue;ansmax(ans,dp[i][used](k-used));}}coutansendl;return0;}