算法三十六：青蛙

妖狐艹你老母 2022-05-21 09:17 226阅读 0赞

### **问题描述** ###

一个坐标轴上有 n 个荷叶，编号从 1 到 n。每片荷叶有一个坐标。

有一只可爱的小青蛙，它任选一片荷叶作为起点，并选择一个方向（左或右）然后开始跳。第一次跳跃时，他没有任何限制。从第二次跳跃开始，受到魔法的影响，他每次跳跃的距离都必须不小于前一次跳跃的距离，且跳跃方向必须与上一次跳跃保持一致。

每一片荷叶上都有一个数值。每次小青蛙跳到一片荷叶上时，他就会获得该荷叶对应的数值。特别地，他初始选择的荷叶的数值也是能得到的。

小青蛙可以在任意时刻选择停止跳跃。

可爱的小青蛙希望能获得尽可能大的数值总和。你能帮帮她吗？

### **输入格式** ###

第一行个整数 n，意义见问题描述。

第 2 行到第 n+1 行，每行 2 个整数 x\[i\] 和 s\[i\]，描述一片荷叶，其中 x\[i\] 表示这片荷叶的坐标，s\[i\] 表示这片荷叶上的数值。

### **输出格式** ###

一行一个整数，表示小青蛙能够获得的最大的数值总和。

### **样例输入** ###

6
    5 6
    1 1
    10 5
    7 6
    4 8
    8 10

### **样例输出** ###

### 具体实现 ###

\#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;  
\}