{"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\\}$ 是好的当且仅当 $\\forall i\\in[1,k)$，$r_i-l_i<r_{i+1}-l_{i+1}$。\n\n简单来说，一个 $01$ 序列是好的当且仅当从左到右形成的极长 $1$ 段长度严格递增。\n\n给定序列 $\\{a_n\\}$，你可以进行如下操作若干次（或不进行操作）：\n\n- 选择 $i,j(i\\ne j)$，交换 $a_i,a_j$。\n\n试求最小的操作次数使得 $\\{a_n\\}$ 变成一个好的序列。\n\n## Input\n\n一行一个长为 $n$（$n\\leq 800$） 的 $01$ 序列 $\\{a_n\\}$。\n\n## Output\n\n一行一个数字，表示答案。\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10164","tags":["动态规划 DP","2024","前缀和","洛谷月赛"],"sample_group":[["01101","1"],["01011","0"]],"created_at":"2026-03-03 11:09:25"}}