一个坐标轴上有 n 个荷叶,编号从 1 到 n。每片荷叶有一个坐标。
有一只可爱的小青蛙,它任选一片荷叶作为起点,并选择一个方向(左或右)然后开始跳。第一次跳跃时,他没有任何限制。从第二次跳跃开始,受到魔法的影响,他每次跳跃的距离都必须不小于前一次跳跃的距离,且跳跃方向必须与上一次跳跃保持一致。
每一片荷叶上都有一个数值。每次小青蛙跳到一片荷叶上时,他就会获得该荷叶对应的数值。特别地,他初始选择的荷叶的数值也是能得到的。
小青蛙可以在任意时刻选择停止跳跃。
可爱的小青蛙希望能获得尽可能大的数值总和。你能帮帮她吗?
第一行个整数 n,意义见问题描述。
第 2 行到第 n+1 行,每行 2 个整数 x[i] 和 s[i],描述一片荷叶,其中 x[i] 表示这片荷叶的坐标,s[i] 表示这片荷叶上的数值。
一行一个整数,表示小青蛙能够获得的最大的数值总和。
#include <bits/stdc++.h> using namespace std; const int N = 1003; pair<int, int> a[N]; int n;
int dp[N][N];
int main() { scanf("%d", &n); for(int i = 1; i <= n; ++i){ int x, y; scanf("%d%d", &x, &y); a[i] = pair<int, int> (x, y); } int ans = 0; for(int round = 0; round < 2; ++round){ sort(a + 1, a + n +1); for(int i = 1; i <= n; ++i){ dp[i][i] = a[i].second; for(int j = 1; j < i; ++j){ dp[i][j] = 0; for(int k = j; k && 2 * a[j].first <= a[i].first + a[k].first; --k) dp[i][j] = max(dp[i][j], dp[j][k]); ans = max(ans, (dp[i][j] += a[i].second)); } } for(int i = 1; i <=n; ++i) a[i].first = -a[i].first; } printf("%d\n",ans); return 0; }