題目

[CSP-J 2022] 上升點列
題目描述
在一個二維平面內，給定 n 個整數點 (x i ,y i? )，此外你還可以自由添加 k 個整數點。
你在自由添加 k 個點后，還需要從 n+k 個點中選出若干個整數點并組成一個序列，使得序列中任意相鄰兩點間的歐幾里得距離恰好為 1 而且橫坐標、縱坐標值均單調不減，即 x i+1 ?x i =1,y i+1 =y i 或 y i+1 ?y i =1,x i+1 =x i 。請給出滿足條件的序列的最大長度。

輸入格式
第一行兩個正整數 n,k 分別表示給定的整點個數、可自由添加的整點個數。接下來 n 行，第 i 行兩個正整數 x i ,y i 表示給定的第 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.各點按x、y排序
2.狀態:到達各點的最多序列
3.狀態轉移:到達該點的最多序列=前面所有點中的最多序列
4.轉移方程:f[i][n]=max(f[i][n],f[j][k-dis(i,j)]+dis(i,j)+1)
f[當前點][借的點數]=max(f[當前點][借的點數],
f[當前點前的每個點][當前借的點數-i到j兩點間需要的點數]
+
i到j兩點間需要的點數
+
i點本身
)
5.三層循環
一層，遍歷每個點(i)
二層，遍歷i前所有點(j)
三層，遍歷能借的點數0到k-dis(i,j)

圖解

兩點間歐幾里得距離

代碼

#include <bits/stdc++.h>
using namespace std;
int n,//整數點數 k,//可添加整數點數 x,y,//整數點的坐標 ans,//最多序列 f[501][101];//在借得不同數點情況下到達每個點的最多序列數 //f[i][x]=max(f[i][x],f[j][x-dis(i,j)]+dis(i,j)+1) 
struct point{int x,y;bool operator<(const point p2)const{if(x==p2.x)return y<p2.y;return x<p2.x;}
}p[501];
int dis(int i2,int i1){return p[i1].x-p[i2].x+p[i1].y-p[i2].y-1;
}
void view(){cout<<"各點"<<endl;for(int i=0;i<n;i++)cout<<p[i].x<<","<<p[i].y<<endl;
}
void view2(){cout<<"最多序列"<<endl;cout<<"添加\t";for(int x=0;x<=k;x++)cout<<x<<'\t';cout<<endl;	for(int i=0;i<n;i++){cout<<p[i].x<<","<<p[i].y<<"\t";for(int x=0;x<=k;x++)cout<<f[i][x]<<'\t';cout<<endl;	}}
int main(){freopen("point.in","r",stdin);cin>>n>>k;for(int i=0;i<n;i++){cin>>x>>y;p[i]=point{x,y}; }//view();sort(p,p+n);view();for(int i=0;i<n;i++){//遍歷所有點 f[i][0]=1;//初始化，每個點序列起碼有1 for(int j=0;j<i;j++)//遍歷前面的所有點 if(p[j].y<=p[i].y){//如果是升序(右上) int m=dis(j,i);//歐幾里得距離 for(int x=0;x+m<=k;x++)//j已經加的點+現在i到j加的點不超過k f[i][x+m]=max(f[i][x+m],f[j][x]+dis(j,i)+1);/*第i點用了x+m個點后的最多序列=以下中最大本來的最多序列i前j點用了x個點后的最多序列，加上i到j需要的點，+i點本身 */	}	}view2();for(int i=0;i<n;i++)//遍歷所有點,不一定是最后一個序列最多 for(int j=0;j<=k;j++)//用添加點最少而序列最多的 ans=max(ans,f[i][j]+k-j);//在必須用的點基礎上還可以用k剩余的點 cout<<ans;return 0;
}

數據