显然，这是一道DP题。
我们看到也许会想到一个最简单的骗分:
输出 -1
( 然而，会获得 0 pts 的好成绩，因为数据中没有 -1。。。。
然后考虑解法.
显然答案单调，我们考虑二分答案，每次对于一个答案，验证是否合法。
然后，我们再看这个验证的 check 怎么写
考虑 dp, fi 表示 跳到 i 能获得的金币数量, 我们有
fi=fj+ai,(从di能跳到dj)
但是 O(n2) , 复杂度爆炸，怎么办？
考虑 到 fi 只和 fj 有关, 可以使用单调队列优化
于是这道题就做完了。。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
| #include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 500000;
const long long neInf = 0x8080808080808080;
struct gezi
{
int dist;
int score;
} a[maxn + 1];
long long dp[maxn + 1];
int q[maxn + 1];
int n, d, k, lb, rb, ans = -1;
long long sum;
long long DP(int left, int right)
{
memset(dp, 0x80, sizeof(dp));
dp[0] = 0;
memset(q, 0, sizeof(q));
int tou = 1, weight = 0, j = 0;
for (int i = 1; i <= n; i++)
{
while (a[i].dist - a[j].dist >= left && j < i)
{
if (dp[j] != neInf)
{
while (tou <= weight && dp[q[weight]] <= dp[j])
weight--;
q[++weight] = j;
}
j++;
}
while (tou <= weight && a[i].dist - a[q[tou]].dist > right)
tou++;
if (tou <= weight)
dp[i] = dp[q[tou]] + a[i].score;
}
long long num = neInf;
for (int i = 1; i <= n; i++)
if (dp[i] > num)
num = dp[i];
return num;
}
int main()
{
cin >> n >> d >> k;
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i].dist);
scanf("%d", &a[i].score);
if (a[i].score > 0)
sum += a[i].score;
}
rb = max(a[n].dist, d);
if (sum < k)
{
cout << "-1" << endl;
return 0;
}
while (lb <= rb)
{
int mid = (lb + rb) / 2;
int l = max(1, d - mid), r = d + mid;
long long num = DP(l, r);
if (num < k)
lb = mid + 1;
else
ans = mid, rb = mid - 1;
}
if(ans == -1) puts("CCF /fad");
else printf("%d\n", ans);
return 0;
}
|