10 条题解

  • 2
    @ 2023-3-4 16:53:57

    观察一下题意，很容易发现和LIS有很大的关系，所以直接考虑dp。但是LIS只是一维的，这是个坐标系上的，所以需要转换一下。

    首先我们设 f(i,j) 为在前 i 个点中 ， 还剩 j 个自由点时连续上升点列的最大值。此时我想想该怎么转移，因为要用到自由点，所以我们考虑通过前面的与该点保持单调上升的点的状态转移。再考虑回LIS的模板部分：

    for(int i=1;i<=n;i++){
	f[i]=1;
	for(int z=1;z<i;z++){
		if(a[z]<a[i]){
			f[i]=max(f[i],f[z]+1);
		}
	}
}

    是不是感觉有点感觉了（

    然后我们只需要再加入一重循环枚举可以使用的自由点个数 ， 然后判断第 z 个点和第 i 个点是否满足单调性 ， 不满足要跳过该点。接着计算第 z 个点和第 i 个点之间需要增加的自由点，计为 d , 然后判断没有使用的自由点（即 j），和还要加上的自由点 d ， 的和是否超过 最多可以加上的点 k ， 超过就要跳掉。如果还满足那么就可以转移了，状态转移方程就是

    f( i , j ) = max{ f( i , j ) , f( z , j + d) + d + 1}

    d = |i.x - z.x| + | i.y - i.z| - 1

    ps:| x | 的意思是 x 的绝对值

    解释一下为什么：首先考虑一下 f( z , j + d) + d + 1 的意义是什么，是不是就是“还剩 j+d 个自由点 再加上到 点 i 的自由点个数加1”

    那么为什么要 + 1 呢？ 因为 d 是没有算上点 i 需要再加上去

    还要注意输入后要先排序一边，不然会转移不了。

    注意最后计算答案的时候我们需要再重新遍历一次整个 f 数组 ， 并且将每个状态上剩余的 j 也加上。因为我们之前转移定义的就是还剩下 j 个自由点的，所以我们要再加上 不然就会寄！

    那么

    OK

    上代码

    #include <bits/stdc++.h>
using namespace std;
const int N = 510;
int f[N][110];
struct node{
	int x,y;
	
}a[N];
int n,k;
inline bool cmp(node a,node b){
	if(a.x == b.x) return a.y < b.y;
	return a.x < b.x;
}
int main(){
	cin >> n >> k;
	for(int i=1;i<=n;i++){
		cin >> a[i].x >> a[i].y;
 	}	
	sort(a + 1,a + n + 1,cmp);
	
	for(int i=1;i<=n;i++){
		f[i][k] = 1;
		for(int j=0;j<=k;j++){
			
			for(int z=1;z<i;z++){
				if(a[i].x < a[z].x || a[i].y < a[z].y) continue; // 维护单调递减 
				int d = abs(a[i].x - a[z].x) + abs(a[i].y - a[z].y) - 1;// i 和 z 之间要加的自由点个数
				 
				if(j + d > k) continue;
				f[i][j] = max(f[i][j] , f[z][j + d] + d + 1); 
			}
		}
	}
	int ans = 0;
	for(int i=1;i<=n;i++){
		for(int j=0;j<=k;j++)
			ans = max(ans , f[i][j] + j);
	}
	cout << ans ;
	return 0;
}
    • 1
      @ 2023-3-4 17:17:52

      题目大意

      在一个二维平面内，给定 n 个整数点 (xi, yi)(xi​,yi​)，此外你还可以自由添加 k 个整数点。

      你在自由添加 k 个点后，还需要从 n +k 个点中选出若干个整数点并组成一个序列，使得序列中任意相邻两点间的欧几里得距离恰好为 1 而且横坐标、纵坐标值均单调不减。请给出满足条件的序列的最大长度。

      思路

      先把点进行排序，然后从第i个枚举到第k个再列出状态转移方程

      代码

      #include<bits/stdc++.h>
using namespace std;
int k,n;
struct node{
	int x,y;
	bool operator<(const node &w) const{
	    if(x==w.x) return y<w.y;
	    return x<w.x;
	}
}a[1111];
int f[501][101];
int main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++ ){
	    cin>>a[i].x>>a[i].y;//输入横坐标和纵坐标
	}
	sort(a+1,a+1+n);
	for(int i=1;i<=n;i++){
		f[i][k]=1;
		for(int j=0;j<=k;j++){
			for(int l=1;l<i;l++){
				if(a[l].x>a[i].x||a[l].y>a[i].y){
					continue;//已经试过直接舍去
				}
				int dx=abs(a[i].x-a[l].x);//两个横坐标的差
				int dy=abs(a[i].y-a[l].y);//两个纵坐标的差
				int d=dx+dy-1;//减去一个重复的点2
				if(j+d>k){
					continue;//要添加的点数超过了k舍去
				}
				f[i][j]=max(f[i][j],f[l][j+d]+d+1);
			}
		}
	}
	int sum=0;
	for(int i=1;i<=n;i++){
		for(int j=0;j<=k;j++){
			sum=max(sum,j+f[i][j]);//对比得最大长度
		}
	}
	cout<<sum;
	return 0;
}
      思想感情

      *😕 *

      • 0
        @ 2023-3-13 22:26:00

        最长不下降子序列：

        这种问题都要先排序:

        struct node
{
	int x,y;
	bool operator<(const node &w/*引用，常量，加快速度*/) const/*返回值常量*/ //定义“<”
	{
		if(x==w.x)return y<w.y;
		return x<w.x;
	}
}a[502];

sort(a+1,a+n+1);

        `

        #include <iostream>
#include <algorithm>
using namespace std;
struct node
{
	int x,y;
	bool operator<(const node &w) const
	{
		if(x==w.x)return y<w.y;
		return x<w.x;
	}
}a[502];
int f[502][102];

int main()
{
	int n,k;
	cin >> n >> k;
	for(int i=1;i<=n;i++)
	{
		cin >> a[i].x >> a[i].y;
	}
	sort(a+1,a+n+1);
	for(int i=1;i<=n;i++)
	{
		f[i][k]=1;
		for (int j=0;j<=k;j++)
		{
			for(int t=1;t<i;t++)
			{
				if(a[t].x>a[i].x||a[t].y>a[i].y)
				{
					continue;
				}
				int dx=abs(a[i].x-a[t].x);
				int dy=abs(a[i].y-a[t].y);
				if(j+dx+dy-1>k)
				{
					continue;
				}
				f[i][j]=max(f[i][j],f[t][j+dx+dy-1]+dx+dy);
			}
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		for (int j=0;j<=k;j++)
		{
			ans=max(ans,j+f[i][j]);
		}
	}
	cout << ans;
	return 0;
}
        • 0
          @ 2023-3-10 21:55:33

          //没发过题解，如不美观请多多谅解 //献上代码 其实这一题就是求在一个二维平面中的最长不下降子序列(LIS).

          #include <iostream> #include <algorithm> #include <vector> #include <map> #include <cmath> #include <queue> using namespace std;

          int N = 510 , K = 110;

          int n , k;

          struct node { int x , y; bool operator< (const node &w) const { if(x == w.x) { return y < w.y; } return x < w.x; } }

          node a[N];

          int lon[N][K];

          int main() { scanf("%d%d" , &n , &k); for(int i = 1;i <= n;i++) { scanf("%d%d" , &a[i].x , &a[i].y); } sort(a + 1 , a + 1 + n); for(int i = 1;i <= n;i++) { lon[i][k] = 1; for(int j = 0;j <= k;j++) { for(int t = 1;t < i;t++) { if(a[t].x > a[i].x || a[t].y > a[i].y) { continue; } int dx = abs(a[i].x - a[t].x); int dy = abs(a[i].y - a[t].y); int d = dx + dy - 1;

          			if(j + d > k)
            {
                continue;
            }
			lon[i][j] = max(lon[i][j] , lon[t][j + d] + 1 + d);
		}
	}
}
int ans = 0;
for(int i = 1;i <= n;i++)
{
	for(int j = 1;j <= k + 1;j++)
	{
		ans = max(ans , j - 1 + lon[i][j - 1]);
	}
}
cout << ans << endl;
return 0;

          }

          • 0
            @ 2023-3-4 16:45:28

            fij表示当前取到第i个点，剩下j 个自由点

            接下来考虑状态转移：

            1. 取到第i个点时没有添加点fij=fi-1j;
            2. 在第i个点的基础上添加了点，设添加了p个（p=xj-xt+yj-yt-1)其中状态转移方程为：fij=max(j+1,fi-1j,fti-j+p+1)

            代码：

            #include<bits/stdc++.h>
using namespace std;
const int N=510,K=110;
int n,k,ans;
struct node{
	int x,y;
}a[N];
int f[N][K];

bool cmp(node a,node b){
	if(a.x!=b.x) return a.x<b.x;
	else return a.y<b.y;
}
int main()
{
	cin>>n>>k;
	for(int i=1;i<=n;i++)
		cin>>a[i].x>>a[i].y;
	sort(a+1,a+1+n,cmp);
	for(int i=1;i<=n;i++)
	{
		f[i][k]=1;
		for(int j=0;j<=k;j++)
		{
			for(int t=1;t<i;t++)
			{
				if(a[t].x>a[i].x||a[t].y>a[i].y)	continue;//要符合题意的序列限制
				int dx=abs(a[i].x-a[t].x);
				int dy=abs(a[i].y-a[t].y);
				int d=dx+dy-1;//求在x,y之间我们要加多少个自由点
				if(j+d>k)	continue;//如果要加的自由点超过k个，就不能再转移了
				f[i][j]=max(f[i][j],f[t][j+d]+d+1);
			}
		}
	}
	for(int i=1;i<=n;i++)
		for(int j=0;j<=k;j++)
		{
			ans=max(ans,j+f[i][j]);
		}
	cout<<ans;
	return 0;
}
            • 0
              @ 2023-3-4 16:43:17

              既然老师要求那就写一下题解吧，正好之前今早刚学完与区间dp有关的芝士。

              题意描述

              在平面上有 n 个点，可以再插入 k 个点。从某个点开始，向右或向下走（要求走到的位均有点），最多可以走多少个点。 有如下明显的性质： 最优解一定会插入 k 个点。 路径中在第一个原有点前面插入点对最优解是没有帮助的，可设最优解一定从原有点开始。

              大致思路

              我们看到n≤500,很容易想到 O(n^3) 的做法。然后这题实际上就是一题二维的LIS（最长不下降子序列）。

              我们需要先把输入的点进行排序，然后设 dp(i,k) 是从第i个枚举到第k个。

              之后就可以非常简单地列出状态转移方程： dp(i,k)=max(dp(i,k-dis(i,j)+1+dis(i,j),dp(i,k))

              OK，上代码

              #include <bits/stdc++.h>
using namespace std;
const int N = 510;
int f[N][110];
struct node{
	int x,y;
	
}a[N];
int n,k;
inline bool cmp(node a,node b){
	if(a.x == b.x) return a.y < b.y;
	return a.x < b.x;
}
int main(){
	cin >> n >> k;
	for(int i=1;i<=n;i++){
		cin >> a[i].x >> a[i].y;
 	}	
	sort(a + 1,a + n + 1,cmp);
	
	for(int i=1;i<=n;i++){
		f[i][k] = 1;
		for(int j=0;j<=k;j++){
			
			for(int z=1;z<i;z++){
				if(a[i].x < a[z].x || a[i].y < a[z].y) continue; // 维护单调递减 
				int d = abs(a[i].x - a[z].x) + abs(a[i].y - a[z].y) - 1;// i 和 z 之间要加的自由点个数
				 
				if(j + d > k) continue;
				f[i][j] = max(f[i][j] , f[z][j + d] + d + 1);
			}
		}
	}
	int ans = 0;
	for(int i=1;i<=n;i++){
		for(int j=0;j<=k;j++)
			ans = max(ans , f[i][j] + j);
	}
	cout << ans ;
	return 0;
}

              完结撒花

              • 0
                @ 2023-3-4 16:37:31

                题目

                在一个二维平面内，给定n个整数点 (Xi,Xi)，此外你还可以自由添加k个整数点。你在自由添加k个点后，还需要从n+k个点中选出若干个整数点并组成一个序列，使 得序列中任意相邻两点间的欧几里得距离恰好为1而且横坐标、纵坐标值均单调不减，求出满足条件的序列的最大长度。

                1≤n≤500，0≤k≤100。对于所有给定的整点，其横纵坐标1≤xi,yi≤10^9

                思路

                排序，枚举，最后得出状态转移方程

                代码

                #include<cmath>
#include<algorithm>
using namespace std;
int n,k;
struct node{
	int x,y;
}a[501];
bool cmp(node i,node k){
	if(i.x==k.x) return i.y<k.y;
	return i.x<k.x;
}
int f[501][101];
int main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>a[i].x>>a[i].y;
	}
	sort(a+1,a+1+n,cmp);
	for(int i=1;i<=n;i++){
		f[i][k]=1;
		for(int j=0;j<=k;j++){
			for(int t=1;t<i;t++){
				if(a[t].x>a[i].x||a[t].y>a[i].y) continue;//维护单调 
				
				int d=abs(a[i].x-a[t].x)+abs(a[i].y-a[t].y)-1;
				if(j+d>k) continue;
				f[i][j]=max(f[i][j],f[t][j+d]+d+1);
			}
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++){
		for(int j=0;j<=k;j++){
			ans=max(ans,j+f[i][j]);//加上剩余的自由点 
		}
	}
	cout<<ans;
	return 0;
}

                题解入口：题解 - 「CSP-J 2022」上升点列（point） - TeMenHu (temege.com)

                • 0
                  @ 2023-3-4 16:22:11 
                  #include<iostream>
#include<algorithm>
using namespace std;
const int N=501,K=101;
int n,k;
struct node{
	int x,y;
}a[N];
int f[N][K];
bool cmp(node a,node b){
	if(a.x==b.x){
		return a.y<b.y;
	}
	return a.x<b.x;
}
int main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>a[i].x>>a[i].y;
	}
	sort(a+1,a+1+n,cmp);
	for(int i=1;i<=n;i++){
		f[i][k]=1;
		for(int j=0;j<=k;j++){
			for(int t=1;t<i;t++){
				if(a[t].x>a[i].x||a[t].y>a[i].y){
					continue;
				}
				int dx=abs(a[i].x-a[t].x);
				int dy=abs(a[i].y-a[t].y);
				int d=dx+dy-1;
				if(j+d>k){
					continue;
				}
				f[i][j]=max(f[i][j],f[t][j+d]+d+1);
			}
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++){
		for(int j=0;j<=k;j++){
			ans=max(ans,j+f[i][j]);
		}
	}
	cout<<ans<<endl;
	return 0;
}
                  • -1
                    @ 2023-3-8 21:07:30

                    首先我们定义好结构体,把输入的点以x为第一关键字,y为第二关键字进行排序

                    struct node{
	int x,y;
	bool operator< (const node &w) const
	{
		if(x==w.x)	return y<w.y;
		return x<w.x;
	}
}a[501];

                    设f[i][j]为枚举到第i个点,还有j个自由点时序列最大长度,则状态转移方程为

                    f[i][j]=max(f[i][j],f[t][j+d+1]

                    t是从1到i-1,d是第i个点和第t个点之间要添加的自由点个数 求完所有序列的长度后,再找出最大长度就做完了

                    代码

                    #include<algorithm>
#include<iostream>
#include<cmath>
using namespace std;
int n,k;
struct node{
	int x,y;
	bool operator< (const node &w) const
	{
		if(x==w.x)	return y<w.y;
		return x<w.x;
	}
}a[501];
int f[501][101];
int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i].x>>a[i].y;
    }
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++){
        f[i][k]=1;//初始没用自由点的值为1
        for(int j=0;j<=k;j++){
            for(int t=1;t<i;t++){
                if(a[t].x>a[i].x||a[t].y>a[i].y)	continue;//不符合题意跳过
                int x=abs(a[i].x-a[t].x);
                int y=abs(a[i].y-a[t].y);
                int d=x+y-1;//要加多少个自由点
                if(j+d>k){//自由点不够
                    continue;
                }
                f[i][j]=max(f[i][j],f[t][j+d]+d+1);
            }
        }
    }
    int ans = 0;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=k;j++){
            ans=max(ans,j+f[i][j]);
        }
    }
    cout<<ans;
    return 0;
}
                    • -1
                      @ 2023-3-4 17:00:30

                      /* 我们从要选点，形成 一个序列 ，可以看出这是一个经典的二维dp题

                      我们进行排列，然后dp

                      f[i][j]的i为以a[i]为结尾的序列，j为剩自由点数量

                      转移方程为 f[i][j]=max(f[i][j],f[t][j+d]+d+1)

                      f[t][j+d]+d+1为第t项结尾 变为 第i项结尾的数列里的数的个数

                      */

                      //献上代码 (QWQ)

                      #include<bits/stdc++.h>

                      using namespace std;

                      int n,k,ans,f[501][101];//f[i][j]的i为以a[i]为结尾的序列，j为剩自由点数量

                      struct node{

                      int x,y;

                      }a[501];

                      bool cmp(node x,node y){//假设x优先级比y高

                      if(x.x==y.x)return x.y<y.y;

return x.x<y.x;

                      }

                      int main(){

                      cin>>n>>k;

for(int i=1;i<=n;i++){
	
	cin>>a[i].x>>a[i].y;
	
}

sort(a+1,a+n+1,cmp);//排列先后顺序，方便dp 

for(int i=1;i<=n;i++){
	
	f[i][k]=1;//初始化 
	
	for(int j=0;j<=k;j++){//枚举自由点 
	
		for(int t=1;t<i;t++){
			
			if(a[t].x>a[i].x||a[t].y>a[i].y)continue;//不满足条件，退出 
			
			int dx=abs(a[i].x-a[t].x);
			
			int dy=abs(a[i].y-a[t].y);
			
			int d=dx+dy-1;//需要的自由点数量 
			
			if(j+d>k)continue; //不够，退出 
			
			f[i][j]=max(f[i][j],f[t][j+d]+d+1);//方程转移式 
			
		}
		
	}
	
}

for(int i=1;i<=n;i++){
	
	for(int j=0;j<=k;j++){
		
		ans=max(ans,f[i][j]+j);//选出最多的序列 
		
	}
	
}

cout<<ans;

return 0;

                      }

                      • 1

                      「CSP-J 2022」上升点列（point）

                      信息

                      ID
                      2919
                      时间
                      1000ms
                      内存
                      256MiB
                      难度
                      8
                      标签
                      递交数
                      109
                      已通过
                      34
                      上传者
                      1. 关于
                      2. 联系我们
                      3. 隐私
                      4. 服务条款
                      5. 版权申诉
                      6. Language
                      7. Theme
                      3. Worker 0 in 39ms
                      4. Powered by Hydro v3.15.13 Community