『PG2』消除萝卜 A

Luogu

IDLGP9899

Time1000ms

Memory512MB

DifficultyP3

贪心

有 $2\times n$ 的两行萝卜，萝卜分白萝卜和红萝卜，我们使用 $a_{i,j}=0/1$ 来表示第 $j$ 行第 $i$ 个萝卜是白萝卜还是红萝卜。你每次可以花 $1$ 的代价，选定一个有萝卜的位置，并将这个萝卜所在的由同种颜色萝卜所构成的四连通极大连通块的萝卜全部拿走，然后一个在第二行的萝卜如果其对应的第一行的位置没有萝卜，就会掉落至第一行。请问拿走所有萝卜的最小代价是多少。 ## Input 第一行包含一个正整数 $n$ 表示每行有多少个萝卜。第二行有 $n$ 个 $0$ 或 $1$ 的整数,其中第 $i$ 个表示 $a_{i,2}$。第三行有 $n$ 个 $0$ 或 $1$ 的整数,其中第 $i$ 个表示 $a_{i,1}$。 ## Output 一行一个整数表示你的答案。 [samples] ## Note 对于所有测试点 $a_{i,j}\in \{0,1\}$，$1\leq n\leq 5\times 10^6$。 **本题使用捆绑测试** $\sf subtask \ 1: n\leq1 \ \ \ \ \ \ \ \ \ \ \ \ \ 10pts$ $\sf subtask \ 2: n\leq10 \ \ \ \ \ \ \ \ \ \ \ 20pts $ $\sf subtask \ 3: n\leq100 \ \ \ \ \ \ \ \ \ 15 pts$ $\sf subtask \ 4: n\leq5000 \ \ \ \ \ \ \ 15 pts$ $\sf subtask \ 5: n\leq500000 \ \ \ 20pts$ $\sf subtask \ 6: n\leq5000000 \ 20pts$

Samples

Input #1

3
0 1 0
1 0 1

Output #1

Input #2

6
1 0 1 0 0 1
1 1 0 1 0 1

Output #2

Input #3

10
0 0 1 1 1 1 1 1 0 0 
0 1 1 0 1 0 0 0 0 1

Output #3

Input #4

10
0 1 0 1 0 1 0 1 0 1
1 0 1 0 1 0 1 0 1 0

Output #4

Input #5

10
1 0 1 1 1 0 0 1 0 1
0 0 0 1 0 1 0 1 1 0

Output #5

API Response (JSON)

{
  "problem": {
    "name": "『PG2』消除萝卜 A",
    "description": {
      "content": "有 $2\\times n$ 的两行萝卜，萝卜分白萝卜和红萝卜，我们使用 $a_{i,j}=0/1$ 来表示第 $j$ 行第 $i$ 个萝卜是白萝卜还是红萝卜。 你每次可以花 $1$ 的代价，选定一个有萝卜的位置，并将这个萝卜所在的由同种颜色萝卜所构成的四连通极大连通块的萝卜全部拿走，然后一个在第二行的萝卜如果其对应的第一行的位置没有萝卜，就会掉落至第一行。 请问拿走所有萝卜的最小代价是多少。",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P3"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9899"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "有 $2\\times n$ 的两行萝卜，萝卜分白萝卜和红萝卜，我们使用 $a_{i,j}=0/1$ 来表示第 $j$ 行第 $i$ 个萝卜是白萝卜还是红萝卜。\n\n你每次可以花 $1$ 的代价，选定一个有萝卜的位置，并将这个萝卜所在的由同种颜色萝卜所构成的四连通极大连通块的萝卜全部拿走，然后一个在第二行的萝卜如果其对应的第一行的位置没有萝卜，就会掉落至第一行。\n\n请问拿走所有萝卜的最小代价是多少。\n...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments