a605. 交錯和
Tags : DP
Accepted rate: 56人/ 74人 ( 76%) [非即時]
評分方式:
Strictly

最近更新 : 2024-04-22 15:17

Content
給定一個整數數列 $\color{black}{\mathbf{a} = a_1, a_2, \ldots, a_n}$。對於每個下標數列 $\color{black}{\mathbf{i} = i_1, i_2, \ldots, i_m}$,其中 $\color{black}{m\ne0}$ 且 $\color{black}{1\le i_1<i_2<\ldots<i_m\le n}$,我們定義交錯和 $\color{black}{\sigma(\mathbf{i}; \mathbf{a})}$ 為 $\color{black}{a_{i_1} - a_{i_2} + a_{i_3} - a_{i_4} + \ldots + (-1)^{m-1}a_{i_m}}$。
 
已知對於所有 $\color{black}{1}$ 到 $\color{black}{m-1}$ 之間的整數 $\color{black}{j}$,均有 $\color{black}{i_{j+1}-i_j \le \delta}$,請求出 $\color{black}{\sigma(\mathbf{i}; \mathbf{a})}$ 的最大值。
Input

$\color{black}{n}$ $\color{black}{\delta}$

$\color{black}{a_1}$ $\color{black}{a_2}$ $\color{black}{\ldots}$ $\color{black}{a_n}$

  • $\color{black}{1 \le n \le 10^6}$。
  • $\color{black}{1 \le \delta \le n}$。
  • 對於所有的 $\color{black}{k \in \{1, 2, \ldots, n\}}$,均有 $\color{black}{-2^{31} \le a_k \le 2^{31}-1}$。
  • 輸入的數皆為整數。
Output
$\color{black}{S}$
  • $\color{black}{S}$ 為一整數,代表在滿足 $\color{black}{i_{j+1}-i_j \le \delta}$ 的限制下,$\color{black}{\sigma(\mathbf{i}; \mathbf{a})}$ 的最大值。
Sample Input #1
5 1
1 4 3 2 5
Sample Output #1
6
Sample Input #2
5 2
1 4 3 2 5
Sample Output #2
7
Sample Input #3
10 4
-10 -9 -8 -7 -6 -5 -4 -3 -2 -1
Sample Output #3
-1
測資資訊:
記憶體限制: 512 MB
不公開 測資點#0 (20%): 0.2s , <1K
不公開 測資點#1 (20%): 0.2s , <1M
不公開 測資點#2 (20%): 0.2s , <1M
不公開 測資點#3 (20%): 0.2s , <10M
不公開 測資點#4 (20%): 0.2s , <10M
Hint :
Tags:
DP
出處:
原創問題,如有雷同,純屬巧合 [管理者: xavier13540 (柊 四千) ]

Status Forum 排行

ID User Problem Subject Hit Post Date
40024 xavier13540 (柊 四千) a605
作者提供的解法
412 2024-04-22 15:05