1 条题解
-
6
思路
$\\$这道题的数据范围不需要最值优化 $\\$首先第一步当然是把这些点按照坐标从小到大排序啦。 $\\$由贝西 只朝一个方向跳跃，所以要分两种情况：一种是一直向右跳，一种是一直向左跳。 当一直向右跳时，定义f[i][j]表示当前贝西已经跳到了第$i$个点，且上一步是从第$j$个点跳到第$i$个点的最大总得分。那么 $\\$f[i][j]=max{f[j][k]+s[i]} 其中$k<=j<i，x(j)−x(k)≤x(i)−x(j)。$ $\\$考虑边界$f[i][i]=s[i]$。（即一开始站在任意一个点上） $\\$当一直向左跳时也同理，只不过方向倒过来而已。只要做两次 DP 就可以了。 $\\$这个时候时间复杂度为 $O(N^3)$。代码
#include <bits/stdc++.h> using namespace std; const int N=105; int n,f[N][N],ans; struct Point{ int x,s; } point[N]; bool cmp(Point a,Point b) { return a.x<b.x; } int main() { cin>>n; for(int i=1;i<=n;i++) cin>>point[i].x>>point[i].s; sort(point+1,point+1+n,cmp); for(int i=1;i<=n;i++) { f[i][i]=point[i].s; for(int j=1;j<i;j++) { int k=j; while(((point[i].x-point[j].x)>=(point[j].x-point[k].x))&&k>0) { f[i][j]=max(f[i][j],f[j][k]+point[i].s); k--; } ans=max(ans,f[i][j]); } } for(int i=n;i>=1;i--) { //f[i][i]=point[i].s; for(int j=n;j>i;j--) { int k=j; while(((point[j].x-point[i].x)>=(point[k].x-point[j].x))&&k<=n) { f[i][j]=max(f[i][j],f[j][k]+point[i].s); k++; } ans=max(ans,f[i][j]); } } cout<<ans; }
yiyun
LV 3
MOD
@ 2023-11-5 20:24:52
- 1