MojaCoder
Playground
Problems
Post Problem
Contests
Create Contest
EN
JA
Sign up
Sign in
E - Doubling
2 secs
1024 MB
bayashiko
Tweet
Problem
Submissions
Test cases
Editorial
dpをします。
d
p
[
l
]
[
r
]
=
dp[l][r]=
d
p
[
l
]
[
r
]
=
区間
[
l
,
r
]
[l,r]
[
l
,
r
]
でこの問題を解いた時の解
とします。
この値は、
l
<
i
<
r
l<i<r
l
<
i
<
r
に対して以下の値を計算した時の最大値です。
2
×
m
a
x
2×\rm{max}
2
×
max
(
d
p
[
l
]
[
i
−
1
]
,
d
p
[
i
+
1
]
[
r
]
)
+
m
i
n
(dp[l][i-1],dp[i+1][r])+\rm{min}
(
d
p
[
l
]
[
i
−
1
]
,
d
p
[
i
+
1
]
[
r
])
+
min
(
d
p
[
l
]
[
i
−
1
]
,
d
p
[
i
+
1
]
[
r
]
)
+
m
a
x
(dp[l][i-1],dp[i+1][r])+\rm{max}
(
d
p
[
l
]
[
i
−
1
]
,
d
p
[
i
+
1
]
[
r
])
+
max
(
A
i
−
1
,
A
i
+
1
)
(A_{i-1},A_{i+1})
(
A
i
−
1
,
A
i
+
1
)
m
o
d
\rm{mod}
mod
m
i
n
\rm{min}
min
(
A
i
−
1
,
A
i
+
1
)
(A_{i-1},A_{i+1})
(
A
i
−
1
,
A
i
+
1
)
計算量は
O
(
N
3
)
O(N^3)
O
(
N
3
)
です。