題目的難度顏色使用 Luogu 上的分級，由簡單到困難分別為 🔴🟠🟡🟢🔵🟣⚫。

🔗 awc0065_c Choosing Flowers for the Flower Bed

Problem Statement

題目簡述

有 NN 朵花排列在一起，每朵花都有一個價值，第 ii 朵花的價值為 AiA_i。
需要選出若干朵花放入花壇，但不能選擇相鄰的兩朵花，求能得到的最大總價值。

Constraints

約束條件

  • 1≤N≤2×1051 \leq N \leq 2 \times 10^5
  • 1≤Ai≤1091 \leq A_i \leq 10^9
  • 所有輸入值皆為整數

思路：打家劫舍

本題的核心限制是「相鄰不能同時選」，這是經典的「打家劫舍」型動態規劃問題，即 198. House Robber 以及其一系列變體，本題事實上就是這個問題的原始版本。

定義 f[i]f[i] 為考慮前 ii 朵花時的最大總價值。對於第 ii 朵花，有兩種選擇：

  1. 選擇第 ii 朵花：那麼第 i−1i-1 朵花就不能選，因此最大總價值為 f[i−2]+Aif[i-2] + A_i。
  2. 不選擇第 ii 朵花：那麼最大總價值就為 f[i−1]f[i-1]。

轉移方程為：

f[i]=max⁡(f[i−2]+Ai,f[i−1])f[i] = \max(f[i-2] + A_i, f[i-1])

複雜度分析

  • 時間複雜度：O(N)\mathcal{O}(N)
  • 空間複雜度：O(N)\mathcal{O}(N)，由於只需要前兩個狀態，可以優化到 O(1)\mathcal{O}(1)。

Code

1
2
3
4
5
6
7
8
9
10
11
12
def solve():
    n = int(input())
    A = list(map(int, input().split()))

    f = [0] * (n + 2)
    for i, x in enumerate(A, start=2):
        f[i] = max(f[i - 2] + x, f[i - 1])
    print(max(f))


if __name__ == "__main__":
    solve()