[DTCPC 2024] 戈布

Luogu

IDLGP10164

Time1000ms

Memory32MB

DifficultyP6

动态规划 DP2024前缀和洛谷月赛

对于 $01$ 序列 $\{a_n\}$，找到最小的 $k$ 满足存在一组 $\{(l_k,r_k)\}$使得以下条件成立。 - $\forall i\in[1,n]$，$a_i=1$ 当且仅当 $\exist j\in[1,k]$，$i\in[l_j,r_j]$。可以证明满足条件的 $\{(l_k,r_k)\}$ 仅有一个。一个 $01$ 序列 $\{a_n\}$ 是好的当且仅当 $\forall i\in[1,k)$，$r_i-l_i<r_{i+1}-l_{i+1}$。简单来说，一个 $01$ 序列是好的当且仅当从左到右形成的极长 $1$ 段长度严格递增。给定序列 $\{a_n\}$，你可以进行如下操作若干次（或不进行操作）： - 选择 $i,j(i\ne j)$，交换 $a_i,a_j$。试求最小的操作次数使得 $\{a_n\}$ 变成一个好的序列。 ## Input 一行一个长为 $n$（$n\leq 800$）的 $01$ 序列 $\{a_n\}$。 ## Output 一行一个数字，表示答案。 [samples]

Samples

Input #1

Output #1

Input #2

Output #2

API Response (JSON)

{
  "problem": {
    "name": "[DTCPC 2024] 戈布",
    "description": {
      "content": "对于 $01$ 序列 $\\{a_n\\}$，找到最小的 $k$ 满足存在一组 $\\{(l_k,r_k)\\}$使得以下条件成立。 - $\\forall i\\in[1,n]$，$a_i=1$ 当且仅当 $\\exist  j\\in[1,k]$，$i\\in[l_j,r_j]$。 可以证明满足条件的 $\\{(l_k,r_k)\\}$ 仅有一个。 一个 $01$ 序列 $\\{a_n\\}$ 是好的当且仅当 $",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 32768
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10164"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "对于 $01$ 序列 $\\{a_n\\}$，找到最小的 $k$ 满足存在一组 $\\{(l_k,r_k)\\}$使得以下条件成立。\n\n- $\\forall i\\in[1,n]$，$a_i=1$ 当且仅当 $\\exist  j\\in[1,k]$，$i\\in[l_j,r_j]$。\n\n可以证明满足条件的 $\\{(l_k,r_k)\\}$ 仅有一个。\n\n一个 $01$ 序列 $\\{a_n\\}$ 是好的当且仅当 $...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments