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
                      上传者