青蛙发表时间:2022-10-27 20:38 青蛙
题目名称:小青蛙时间限制:5 sec 空间限制:256 MB 问题描述 一个坐标轴上有 n 个荷叶,编号从 1 到 n。每片荷叶有一个坐标。 有一只可爱的小青蛙,它任选一片荷叶作为起点,并选择一个方向(左或右)然后开始 跳。第一次跳跃时,他没有任何限制。从第二次跳跃开始,受到魔法的影响,他每次跳跃的距离都必须不小于前一次跳跃的距离,且跳跃方向必须与上一次跳跃保持一致。 每一片荷叶上都有一个数值。每次小青蛙跳到一片荷叶上时,他就会获得该荷叶对应的数值。特别地,他初始选择的荷叶的数值也是能得到的。 小青蛙可以在任意时刻选择停止跳跃。 可爱的小青蛙希望能获得尽可能大的数值总和。你能帮帮她吗? 输入格式 第一行个整数 n,意义见问题描述。 第 2 行到第 n+1 行,每行 2 个整数 x[i] 和 s[i],描述一片荷叶,其中 x[i] 表示这片荷叶的坐标,s[i] 表示这片荷叶上的数值。 输格式 一行一个整数,表示小青蛙能够获得的最大的数值总和。 样例输入 76 48 810 样例输 数据范围 对于 30% 的测试点,保证 n<=8。对于 50% 的测试点,保证 n<=120。对于 70% 的测试点,保证 n<=600。 对于 100% 的测试点,保证 1<=n<=1000,0<=x[i],p[i]<=10^6。 代码 #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; |