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
79
80
81
82
83
84
85
86
87
88
89
| #include <bits/stdc++.h>
#define LL long long
using namespace std;
template <class T>
inline void read(T &res)
{
res = 0;
bool flag = 0;
char c = getchar();
while (c < '0' || '9' < c) { if (c == '-') flag = 1; c = getchar(); }
while ('0' <= c && c <= '9') res = (res << 3) + (res << 1) + (c ^ 48), c = getchar();
if (flag) res = -res;
}
template <class T, class... ARC>
inline void read(T &res, ARC &...com) { read(res), read(com...); }
template <class T>
void write(T res)
{
if (res < 0) putchar('-'), res = -res;
if (res > 9) write(res / 10);
putchar(res % 10 + '0');
}
template <>
inline void write(char c) { putchar(c); }
template <>
inline void write(char *s) { while (*s) putchar(*s++); }
template <class T, class... ARC>
inline void write(T res, ARC... com) { write(res), write(com...); }
const int N = 5005;
const LL Inf = 1e18;
int n, s, t;
struct Node{
LL val, a, b, c, d;
}type[N];
LL f[N][N];
inline LL calc_merge(int x)
{
return type[x].val + type[x].c + type[x].val + type[x].a;
}
inline LL calc_split(int x)
{
return type[x].b - type[x].val + type[x].d - type[x].val;
}
inline LL get_front(int x)
{
return type[x].c + type[x].b;
}
inline LL get_back(int x)
{
return type[x].d + type[x].a;
}
int main()
{
read(n, s, t);
for(int i = 1;i <= n;i ++) read(type[i].val);
for(int i = 1;i <= n;i ++) read(type[i].a);
for(int i = 1;i <= n;i ++) read(type[i].b);
for(int i = 1;i <= n;i ++) read(type[i].c);
for(int i = 1;i <= n;i ++) read(type[i].d);
for(int i = 0;i <= n + 1;i ++)
for(int j = 0;j <= n + 1;j ++)
f[i][j] = Inf;
f[0][0] = 0;
for(int i = 1;i <= n;i ++)
{
for(int j = 1;j <= i;j ++)
{
if(i == s)
{
f[i][j] = min(f[i][j], f[i - 1][j - 1] - type[i].val + type[i].d);
f[i][j] = min(f[i][j], f[i - 1][j] + type[i].val + type[i].c);
}
else if(i == t)
{
f[i][j] = min(f[i][j], f[i - 1][j - 1] - type[i].val + type[i].b);
f[i][j] = min(f[i][j], f[i - 1][j] + type[i].val + type[i].a);
}
else{
if(i < s || j > 1) f[i][j] = min(f[i][j], f[i - 1][j] + get_front(i));
if(i < t || j > 1) f[i][j] = min(f[i][j], f[i - 1][j] + get_back(i));
f[i][j] = min(f[i][j], f[i - 1][j + 1] + calc_merge(i));
f[i][j] = min(f[i][j], f[i - 1][j - 1] + calc_split(i));
}
if(i >= s && i >= t && i != n) f[i][1] = Inf;
}
}
write(f[n][1]);
return 0;
}
|