10 条题解
-
2刘子锐 (liuzr) LV 6 @ 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; }
-
12023-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; }
思想感情*😕 * -
02023-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; }
-
02023-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;
}
-
02023-3-4 16:45:28@
fij表示当前取到第i个点,剩下j 个自由点
接下来考虑状态转移:
- 取到第i个点时没有添加点fij=fi-1j;
- 在第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; }
-
02023-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; }
完结撒花
-
02023-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; }
-
02023-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; }
-
-12023-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; }
-
-12023-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
信息
- ID
- 2919
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 8
- 标签
- 递交数
- 109
- 已通过
- 34
- 上传者