1 条题解
-
5
思路
这一道题的数据范围需要最值优化的： $\\$考虑上一题的状态转移方程： $\\ f[i][j]=max(f[j][k]+point[i].s)$ $\\$其中$k<=j<i,x(j)−x(k)≤x(i)−x(j)。$ $\\$通过分离与$k$无关的常量，可以改写为: $\\ f[i][j]=max(f[j][k])+point[i].s$ $\\$其中$k<=j<i,x(j)−x(k)≤x(i)−x(j)$。 $\\$可以定义$val$为满足这个范围中的$f[j][k]$的最大值。 $\\$但是我们会发现如果我们固定$i$，增加$j$取值时，由于第一个条件$k<=j<i$.$k$的取值范围会增加，但是因为第二个条件$x(j)−x(k)≤x(i)−x(j)$,$k$的取值范围反而会减少。 $\\$但是如果我们固定$j$，增加$i$取值时,$k$的取值范围会一直增加，因为有上界$j$。所以我们可以更改循环顺序，外层循环$j$，中层循环$i$，然后使用$while$循环，添加$i$增加时新符合要求的$k$，最后用$val$维护$f[i][j]$ $\\$这种做法虽然还是3层循环，但是无论是当外层循环变量$j$固定时，最内层的$k$只会最多从$j-1$遍历到$1$。真实的时间复杂度只有$O(n^2)$代码
#include <bits/stdc++.h> using namespace std; const int N=2005; 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 j=1;j<=n;j++) { f[j][j]=point[j].s; int val=f[j][j]; int k=j; for(int i=j+1;i<=n;i++) { while(((point[i].x-point[j].x)>=(point[j].x-point[k].x))&&k>0) { val=max(val,f[j][k]); k--; } f[i][j]=val+point[i].s; ans=max(ans,f[i][j]); } } for(int j=n;j>=1;j--) { int val=f[j][j]; int k=j; for(int i=j-1;i>=1;i--) { while(((point[j].x-point[i].x)>=(point[k].x-point[j].x))&&k<=n) { val=max(val,f[j][k]); k++; } f[i][j]=val+point[i].s; ans=max(ans,f[i][j]); } } cout<<ans; }
yiyun
LV 3
MOD
@ 2023-11-5 20:25:56
- 1