企业官网建设流程全解析

题目描述

在二维平面上给定 n 个整数点，允许自由添加最多 k 个整数点。选出若干点组成序列：
相邻两点欧几里得距离等于 1，只能向右(+1,0)或者向上(0,+1)；
横纵坐标均单调不减；
求序列的最大长度。

序列的长度 = 原始选出来的点数量 + 我们自由添加的点数量。

关键点理解

序列只能向右、向上走，所以整个序列的点满足 x 不下降、y 不下降。
已有两点j(x1,y1)，必须满足x2>=x1,y2>=y1。
两点欧几里得距离：d=(x2-x1)+(y2-y1)；想要把两点连成连续路径，中间需要补dx+dy-1个新增点。
没有用完的新增点，可以全部接在序列的末尾，继续向右 / 向上延伸，每一个新增点都贡献序列长度。

20分暴力DFS

思路:
枚举原始点的全部子集，子集数量2^n。

1. 把子集内点排序，检查是否满足(x,y)单调不减；
2. 计算把这些点串起来一共需要多少新增点 cost；
3. 如果cost<=k，代表这个子集可行。总长度 = 子集大小+(k-cost)。

#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());//单调性的检查for(inti=1;i<cur.size();i++){if(cur[i].first<cur[i-1].first||cur[i].second<cur[i-1].second){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=1;i<=n;i++){intx,y;cin>>x>>y;p.push_back({x,y});}vector<int>c;dfs(0,c);cout<<maxn+k;return0;}

AC解一：记忆化dfs

思路：

1. 点先排序：按 x 升序，x 相同 y 升序。j > i 保证p[j].x>=p[i].x。
2. dfs(i,used)：当前以第 i 号原始点作为序列结尾，已经消耗used个新增点，能选出最多多少个原始点。
3. 从 i 向后枚举每一个j(j>i)，满足yj>=yi，计算连接 i 到 j 需要补充的点need=dx+dy-1。
4. 如果总消耗 (used+need \le k)，就可以跳去 j：dfs(j,used+need)+1（原始点数目 + 1）。
5. memo[i][used]记忆化缓存，避免重复递归计算。
6. 初始：每一个点作为起点，初始消耗used=0，调用dfs(i,0)得到该起点最多原始点数量。
7. 输出写的 maxn+k。

#include<bits/stdc++.h>usingnamespacestd;intn,k;vector<pair<int,int>>p;intmemo[505][505];intmaxn=0;intdfs(inti,intused){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());vector<int>c;memset(memo,-1,sizeof(memo));for(inti=0;i<n;i++){maxn=max(maxn,dfs(i,0));}cout<<maxn+k;return0;}

AC解二：DP

DP定义：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，当used+need <= k，代表资源够用：
dp[i][used+need]=max(dp[i][used+need],dp[j][used]+1)含义：原来以 j 结尾，消耗used个点；连上 i 之后，多消耗need个点，原始点数量 + 1。

#include<bits/stdc++.h>usingnamespacestd;constintMAXN=505;constintMAXK=105;intn,k;vector<pair<int,int>>p;intdp[MAXN][MAXK];intmain(){cin>>n>>k;for(inti=0;i<n;i++){intx,y;cin>>x>>y;p.emplace_back(x,y);}sort(p.begin(),p.end());memset(dp,0,sizeof(dp));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++){if(dp[j][used]==0)continue;dp[i][used+need]=max(dp[i][used+need],dp[j][used]+1);}}}intans=0;for(inti=0;i<n;i++){for(intused=0;used<=k;used++){if(dp[i][used]==0)continue;ans=max(ans,dp[i][used]+(k-used));}}cout<<ans<<endl;return0;}