true
Go
COCI2017-2018#7
省选/NOI-
#9d3dcf
首先我们需要知道，我们经过一个房间就一定会把里面的小精灵拿来换糖吃，所以我们只需要关注自己到或者没到某一个小精灵的房间，这样就可以直接离散化，把题目中的 $n$ 减少了一个数量级。
我们考虑怎么转移。
因为我们经过的区间一定是空的，同时我们经过的区间一定是连续的，那么我们可以考虑尝试扩展我们当前已经走过的区间。
那我们记 $f(l,r,t,[0/1])$，为当前我们已经走过了区间 $[l,r]$，使用的时间为 $t$，现在在区间的左端点/右端点处。
然后考虑我们是如何扩展到当前区间的：
$$
\begin{align}
f(l,r,t,0) &= \max(f(l+1,r,\max(t-dis(a_l,a_{l+1}),0),0),f(l+1,r,\max(t-dis(a_l,a_r),0),1)) + b_l[t<c_l] \\
f(l,r,t,1) &= \max(f(l,r-1,\max(t-dis(a_r,a_{r-1}),0),1),f(l,r-1,\max(t-dis(a_l,a_r),0),0)) + b_r[t<c_r]
\end{align}
$$
题目顺便帮我们指定了开始的位置 $k$，这样我们可以用一个空的精灵 $\{k,0,0\}$ 来作为开始位置，当然如果 $k$ 的位置上已经有了精灵那就直接用就好了。
然后是对区间赋初值。
我们首先对每一个小精灵算出从起点直奔其所在位置的答案：
1
2
3
4
| for(int i = st + 1; i <= m; i++)
f[st][i][dis(st, i)][1] = f[st][i - 1][dis(st, i - 1)][1] + (dis(st, i) < a[i].t ? a[i].b : 0);
for(int i = st - 1; i; i--)
f[i][st][dis(i, st)][0] = f[i + 1][st][dis(i + 1, st)][0] + (dis(st, i) < a[i].t ? a[i].b : 0);
|
然后是转移：
我们在外层枚举时间 $t$，然后再内层从 $[k,k]$ 开始枚举区间。
时间最大枚举到 $\max_{i=1}^m(t_i)$，再往后枚举的话答案绝对不会增加。
1
2
3
4
5
6
7
8
9
10
11
| for(int t = 1; t <= maxt; t++)
{
for(int l = st - 1; l >= 1; l--)
{
for(int r = st + 1; r <= m; r++)
{
f[l][r][t][0] = max(f[l + 1][r][max(t - dis(l, l + 1), 0)][0], f[l + 1][r][max(t - dis(l, r), 0)][1]) + (t < a[l].t ? a[l].b : 0);
f[l][r][t][1] = max(f[l][r - 1][max(t - dis(r, r - 1), 0)][1], f[l][r - 1][max(t - dis(l, r), 0)][0]) + (t < a[r].t ? a[r].b : 0);
}
}
}
|
答案的话就在每一次转移的时候统计一下就好了。
代码如下：
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
| #define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 110, M = 2010;
int n, m, k;
struct Node
{
int a, b, t;
bool operator < (const Node &rhs)const { return a < rhs.a; }
};
Node a[N];
int dis(int i, int j) { return abs(a[i].a - a[j].a); }
int f[N][N][M][2];
int main()
{
int maxt = 0;
scanf("%d%d%d", &n, &k, &m);
bool flag = false;
for(int i = 1; i <= m; i++)
{
scanf("%d%d%d", &a[i].a, &a[i].b, &a[i].t);
if(a[i].a == k)flag = true;
maxt = max(maxt, a[i].t);
}
if(!flag)a[++m] = { k,0,0 };
sort(a + 1, a + 1 + m);
int st = -1;
for(int i = 1; i <= m; i++)
if(a[i].a == k)st = i;
int ans = 0;
memset(f, -63, sizeof(f));
f[st][st][0][0] = f[st][st][0][1] = a[st].b;
for(int i = st + 1; i <= m; i++)
{
f[st][i][dis(st, i)][1] = f[st][i - 1][dis(st, i - 1)][1] + (dis(st, i) < a[i].t ? a[i].b : 0);
ans = max(ans, f[st][i][dis(st, i)][1]);
}
for(int i = st - 1; i; i--)
{
f[i][st][dis(i, st)][0] = f[i + 1][st][dis(i + 1, st)][0] + (dis(st, i) < a[i].t ? a[i].b : 0);
ans = max(ans, f[i][st][dis(st, i)][0]);
}
for(int t = 1; t <= maxt; t++)
{
for(int l = st - 1; l >= 1; l--)
{
for(int r = st + 1; r <= m; r++)
{
f[l][r][t][0] = max(f[l + 1][r][max(t - dis(l, l + 1), 0)][0], f[l + 1][r][max(t - dis(l, r), 0)][1]) + (t < a[l].t ? a[l].b : 0);
f[l][r][t][1] = max(f[l][r - 1][max(t - dis(r, r - 1), 0)][1], f[l][r - 1][max(t - dis(l, r), 0)][0]) + (t < a[r].t ? a[r].b : 0);
ans = max(ans, max(f[l][r][t][0], f[l][r][t][1]));
}
}
}
printf("%d\n", ans);
return 0;
}
|