阿里网站建设需要准备什么软件,免费做视频相册的网站,网站建设资讯平台,工程建设比选公告固价方式网站题目描述
在一个二维平面内#xff0c;给定 n 个整数点 (xi,yi)#xff0c;此外你还可以自由添加 k 个整数点。
你在自由添加 k 个点后#xff0c;还需要从 nk 个点中选出若干个整数点并组成一个序列#xff0c;使得序列中任意相邻两点间的欧几里得距离恰好为 1 而且…题目描述
在一个二维平面内给定 n 个整数点 (xi,yi)此外你还可以自由添加 k 个整数点。
你在自由添加 k 个点后还需要从 nk 个点中选出若干个整数点并组成一个序列使得序列中任意相邻两点间的欧几里得距离恰好为 1 而且横坐标、纵坐标值均单调不减即 xi1−xi1,yi1yi 或 yi1−yi1,xi1xi。请给出满足条件的序列的最大长度。
输入格式
第一行两个正整数 n,k 分别表示给定的整点个数、可自由添加的整点个数。
接下来 n 行第 i 行两个正整数 xi,yi 表示给定的第 i 个点的横纵坐标。
输出格式
输出一个整数表示满足要求的序列的最大长度。
输入输出样例
输入 #1
8 2
3 1
3 2
3 3
3 6
1 2
2 2
5 5
5 3
输出 #1
8
输入 #2
4 100
10 10
15 25
20 20
30 30
输出 #2
103
说明/提示
【数据范围】
保证对于所有数据满足1≤n≤5000≤k≤100。对于所有给定的整点其横纵坐标 1≤xi,yi≤10^9且保证所有给定的点互不重合。对于自由添加的整点其横纵坐标不受限制。
测试点编号n≤k≤xi,yi≤1∼2100103∼4101001005∼750001008∼10500010^911∼1550010010016∼2050010010^9
#include bits/stdc.h
using namespace std;struct node
{int x,y;//1e9 1e9
};
bool operator(node n1,node n2)
{return n1.xn2.x||(n1.xn2.xn1.yn2.y);
}
node p[510];//5e2
int dp[510][110];//5e2
int main()
{int n,k;//5e2 1e2cinnk;for(int i1;in;i){int x,y;//1e9 1e9cinxy;p[i]{x,y};}sort(p1,pn1);int maxn0;//5e2for(int i1;in;i){int xp[i].x,yp[i].y;for(int l0;lk;l){for(int j1;ji;j){int dxx-p[j].x,dyy-p[j].y;if(dx0dy0dxdyl1)dp[i][l]max(dp[i][l],dp[j][l-dx-dy1]dxdy);}if(dp[i][l]0)dp[i][l]l1;maxnmax(maxn,dp[i][l]);}}coutmaxn;return 0;
}
---------------------------------------前方级别洛谷黄题2022CSP-J T3---------------------------------------
主体思想及算法 DP中的LIS最长上升子序列变形。 LIS模板
for(int i1;in;i)
{dp[i]1;for(int j1;ji;j)if(a[i]a[j])dp[i]max(dp[i],dp[j]1);maxnmax(maxn,dp[i]);
}
coutmaxn; 变形后dp[i][j]代表第i个点加j个点的最大答案。
代码解读 main()输入n、k、xi、yi。xi和yi记录在一个node见node类型的p数组里p[i]代表编号为i的一组xy。但是由于下方某些原因p数组不得使用原顺序需要按排序具体规则见operator()后的顺序。排序后定义一个maxn由于此题为LIS变形这个maxn自然代表答案啦不过初始置为k1因为但凡有一个点他添加k个点也有k1了。 第一层循环首先不管加点的事儿先定义xy分别为p[i]的xy一会儿将多次使用。 第二层循环请注意这层循环的变量l代表可以加l个点是从0到k因为你可以选择独自优秀不须加点。 第三层循环这个j也要注意是到i-1由于之前的排序我们保证到i之后肯定都不行了所以也都没用了。再设两个临时变量dx和dy代表x-p[j].x和y-p[j].y同样一会儿将多次使用。如果dx和dy均大于等于0也就是说按照要求可以连线且dx加dy小于等于l加1这里注意加1因为假设l是0dx加dy就得是1。如果满足上句话这些条件那么dp[i][j]就maxdp[j][l-dx-dy1]dxdy。 回到第二层循环因为每一个dp[i][l]都是独立的所以maxn等要在此处单独结算。注意如果dp[i][l]是0要给他设为l1毕竟添加l个点就有l1了。最后maxn maxdp[i][l]。 回到主函数输出maxn。 node一个x一个y。 operator()重载小于运算符如果x不同x小者小否则y小者小。
