品牌建设项目申报,吉林网络营销方式优化,昆明网站建设系统,百度推广培训机构P3089 [USACO13NOV] Pogo-Cow S 弹簧踩高跷
洛谷题目传送门 文章目录 P3089 [USACO13NOV] Pogo-Cow S 弹簧踩高跷题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1 提示题目大意方法一#xff08;线段树维护dp#xff09;code 方法二 #xff08;单调队列维护dp线段树维护dpcode 方法二 单调队列维护dpcode 题目描述
In an ill-conceived attempt to enhance the mobility of his prize cow Bessie, Farmer John has attached a pogo stick to each of Bessie’s legs. Bessie can now hop around quickly throughout the farm, but she has not yet learned how to slow down.
To help train Bessie to hop with greater control, Farmer John sets up a practice course for her along a straight one-dimensional path across his farm. At various distinct positions on the path, he places N targets on which Bessie should try to land (1 N 1000). Target i is located at position x(i), and is worth p(i) points if Bessie lands on it. Bessie starts at the location of any target of her choosing and is allowed to move in only one direction, hopping from target to target. Each hop must cover at least as much distance as the previous hop, and must land on a target.
Bessie receives credit for every target she touches (including the initial target on which she starts). Please compute the maximum number of points she can obtain.
FJ给奶牛贝西的脚安装上了弹簧使它可以在农场里快速地跳跃但是它还没有学会如何降低速度。
FJ觉得让贝西在一条直线的一维线路上进行练习他在不同的目标点放置了N (1 N 1000)个目标点目标点i在目标点x(i)该点得分为p(i)。贝西开始时可以选择站在一个目标点上只允许朝一个方向跳跃从一目标点跳到另外一个目标点每次跳跃的距离至少和上一次跳跃的距离相等并且必须跳到一个目标点。
每跳到一个目标点贝西可以拿到该点的得分请计算他的最大可能得分。
输入格式
* Line 1: The integer N.
* Lines 2…1N: Line i1 contains x(i) and p(i), each an integer in the range 0…1,000,000.
输出格式
* Line 1: The maximum number of points Bessie can receive.
样例 #1
样例输入 #1
6
5 6
1 1
10 5
7 6
4 8
8 10样例输出 #1
25提示
There are 6 targets. The first is at position x5 and is worth 6 points, and so on.
Bessie hops from position x4 (8 points) to position x5 (6 points) to position x7 (6 points) to position x10 (5 points).
题目大意
草场上有一条直线直线上有若干个目标点。每个目标点都有一个分值和一个坐标。现在你可以选择其中任意一个目标点开始跳只能沿一个方向跳并且必须跳到另一个目标点。且每次跳的距离都不能少于上一次的距离。请问你能得到的最大分值是多少、
方法一线段树维护dp
考试时就是想到了这个做法但是改了时限100ms过不了
设 f i , j f_{i , j} fi,j 表示只通过 j j j 步到达点 i i i 的最大分值。 j j j 会炸空间 j j j 其实最多只有 n 2 n^2 n2 种可能乱搞一下就好了
那么 f i , j M a x k 1 i − 1 ( M a x l 0 j f k , l p i ) f_{i , j} Max_{k 1}^{i - 1}(Max_{l 0}^jf_{k , l} p_i) fi,jMaxk1i−1(Maxl0jfk,lpi) 用线段树维护一下 f k , l f_{k , l} fk,l 就好了
code
#include bits/stdc.h
#define fu(x, y, z) for (int x y; x z; x)
#define fd(x, y, z) for (int x y; x z; x--)
#define LL long long
using namespace std;
const int N 1005, M 1000005;
struct node {int x, p;
} t[N];
LL ans;
int n, cnt, flg[M], p[M], p1[M], K 1000005, len, dis[N][N];
struct Tr {LL val;int lp, rp;
} tr[M * 8];
bool cmp(node x, node y) { return x.x y.x; }
void glp(int x) { tr[x].lp len; }
void grp(int x) { tr[x].rp len; }
void updata(int x) { tr[x].val max(tr[tr[x].lp].val, tr[tr[x].rp].val); }
void change(int x, int l, int r, int pos, LL v) {if (l r)tr[x].val max(tr[x].val, v);else {int mid l r 1;if (pos mid) {if (!tr[x].lp)glp(x);change(tr[x].lp, l, mid, pos, v);} else {if (!tr[x].rp)grp(x);change(tr[x].rp, mid 1, r, pos, v);}updata(x);}
}
int query(int x, int l, int r, int pos) {if (r pos)return tr[x].val;else {int mid l r 1, max1 0, max2 0;if (tr[x].lp)max1 query(tr[x].lp, l, mid, pos);if (mid pos tr[x].rp)max2 query(tr[x].rp, mid 1, r, pos);return max(max1, max2);}
}
void clear(int x) {if (tr[x].lp)clear(tr[x].lp);if (tr[x].rp)clear(tr[x].rp);tr[x].val tr[x].lp tr[x].rp 0;
}
void fans() { fu(i, 1, n) ans max(ans, tr[i].val); }
int main() {scanf(%d, n);fu(i, 1, n) scanf(%d%d, t[i].x, t[i].p);sort(t 1, t n 1, cmp);fu(i, 1, n) fu(j, 1, n) dis[i][j] abs(t[i].x - t[j].x);fu(i, 1, n) fu(j, 1, n) {if (!flg[dis[i][j]]) {flg[dis[i][j]] 1;p[cnt] dis[i][j];K max(K, dis[i][j]);}}sort(p 1, p cnt 1);fu(i, 1, cnt) p1[p[i]] i;len n;fu(i, 1, n) {ans max(ans, 1ll * t[i].p);change(i, 0, K, p1[0], 1ll * t[i].p);}int k, k2;fu(i, 1, n) {fu(j, 1, i - 1) {k query(j, 0, K, p1[dis[i][j]]);k2 query(i, 0, K, p1[dis[i][j]]);if (k t[i].p k2)change(i, 0, K, p1[dis[i][j]], k t[i].p);}}fans();fu(i, 1, n) clear(i);len n;fu(i, 1, n) change(i, 0, K, p1[0], t[i].p);fd(i, n, 1) {fd(j, n, i 1) {k query(j, 0, K, p1[dis[i][j]]);k2 query(i, 0, K, p1[dis[i][j]]);if (k t[i].p k2)change(i, 0, K, p1[dis[i][j]], k t[i].p);}}fans();printf(%lld, ans);
}然后因为查找函数没有加等号 就寄掉8分。
差点就AK了 方法二 单调队列维护dp
设 f i , j f_{i , j} fi,j 表示从 j j j 到 i i i 的最大分值 用单调队列维护
好像宏定义会慢一点
code #include bits/stdc.h
#define LL long long
#define fu(x , y , z) for(int x y ; x z ; x )
using namespace std;
const int N 2005;
struct node {int x , p;
} t[N];
int n , k;
LL ans , f[N][N];
inline bool cmp (node x , node y) { return x.x y.x; }
inline bool cmp1 (node x , node y) { return x . x y.x; }
inline void fans (int flg) {memset (f , -0x3f , sizeof (f));if (flg 1) sort (t 1 , t n 1 , cmp);else sort (t 1 , t n 1 , cmp1);for (int j 1 ; j n ; j ) {f[j][j] t[j].p;for (int i j 1 , k j 1 ; i n ; i ) {f[i][j] f[i - 1][j] - t[i - 1].p;while (k 1 (t[j].x - t[k - 1].x) * flg (t[i].x - t[j].x )* flg)f[i][j] max (f[i][j] , f[j][--k]);f[i][j] t[i].p;ans max (ans , f[i][j]);}ans max (ans , f[j][j]);}
}
int main () {scanf (%d , n);fu (i , 1 , n) scanf (%d%d , t[i].x , t[i].p);sort (t 1 , t n 1 , cmp);fans (1);fans (-1);printf (%lld , ans);return 0;
}
