[BCSP-X 2024 12 月初中组] 序列选择

Luogu

IDLGB4163

Time1000ms

Memory256MB

DifficultyP3

动态规划 DP2024北京线性 DPBCSP-X

给定两个长度为 $ n $ 的序列 $ a, b $，找出一个长为 $ n $ 的序列 $ c $，满足对于 $ i = 1, 2, \cdots, n $，有 $ c_i = a_i $ 或 $ c_i = b_i $，使得 $\sum_{i=2}^{n} |c_i - c_{i-1}|$ 最小，你只需要输出这个最小值。 ## Input - 输入的第一行包含一个正整数 $ n $。 - 接下来一行 $ n $ 个整数，表示序列 $ a_i $。 - 接下来一行 $ n $ 个整数，表示序列 $ b_i $。 ## Output 输出一行一个整数，表示 $\sum_{i=2}^{n} |c_i - c_{i-1}|$ 的最小值。 [samples] ## Note ### 样例 1 解释令序列 $ c = [2, 3, 4, 2, 1] $，此时 $\sum_{i=2}^{n} |c_i - c_{i-1}| = 5$，可以证明不存在更小的答案。 ### 样例 2 见附件的 `seq/seq2.in` 与 `seq/seq2.ans`。 ### 数据范围 - 对于 $20\%$ 的数据，满足 $n\leq 20$。 - 对于 $100\%$ 的数据，满足 $1\leq n\leq 2\times 10^5$，$0\leq |a_i|,|b_i|\leq 10^9$。

Samples

Input #1

5
1 3 4 2 5
2 5 4 2 1

Output #1

API Response (JSON)

{
  "problem": {
    "name": "[BCSP-X 2024 12 月初中组] 序列选择",
    "description": {
      "content": "给定两个长度为 $ n $ 的序列 $ a, b $，找出一个长为 $ n $ 的序列 $ c $，满足对于 $ i = 1, 2, \\cdots, n $，有 $ c_i = a_i $ 或 $ c_i = b_i $，使得 $\\sum_{i=2}^{n} |c_i - c_{i-1}|$ 最小，你只需要输出这个最小值。",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": {
      "LuoguStyle": "P3"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGB4163"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给定两个长度为 $ n $ 的序列 $ a, b $，找出一个长为 $ n $ 的序列 $ c $，满足对于 $ i = 1, 2, \\cdots, n $，有 $ c_i = a_i $ 或 $ c_i = b_i $，使得 $\\sum_{i=2}^{n} |c_i - c_{i-1}|$ 最小，你只需要输出这个最小值。\n\n## Input\n\n- 输入的第一行包含一个正整数 $ n $。\n- 接...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments