{"problem":{"name":"[USACO05OPEN] Landscaping G","description":{"content":"农夫约翰正在做一次艰难的转型，从养山羊改成养奶牛，他的农场，由于是为养山羊而设计的所以有太多的山，为了养牛就必须将它整平。但是，将山整平是件很花钱的工作，所以他要移走尽可能少的土。 由于农场很细长，所以可以用一个 $n$ 和 $n$ 个整数（范围 $[1,10^6]$）组成的二维的数组来表示，如： ``` 1 2 3 3 3 2 1 3 2 2 1 2 ``` 上述农场的侧面图是这样的： ","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":500,"memory_limit":65536},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9835"},"statements":[{"statement_type":"Markdown","content":"农夫约翰正在做一次艰难的转型，从养山羊改成养奶牛，他的农场，由于是为养山羊而设计的所以有太多的山，为了养牛就必须将它整平。但是，将山整平是件很花钱的工作，所以他要移走尽可能少的土。\n\n由于农场很细长，所以可以用一个 $n$ 和 $n$ 个整数（范围 $[1,10^6]$）组成的二维的数组来表示，如：\n\n```\n1 2 3 3 3 2 1 3 2 2 1 2\n```\n\n上述农场的侧面图是这样的：\n\n```\n    * * *     *\n  * * * * *   * * *   *\n* * * * * * * * * * * *\n1 2 3 3 3 2 1 3 2 2 1 2\n```\n\n一个或是一些连续等高的地面，如果它左边与右边的海拔都比它低的话，就被称为山顶，上面的例子就有三个山顶。 确定如果要使地图上仅有 $k$ 个山顶，至少要移走多少体积的土（每块地面减少一单位海拔需移走一单位的土）。注意，地面的海拔只能被降低不能被升高。 对于例子，如果要减少到只有 $1$ 个山顶，这需要移走 $2+1+1+1=5$ 个单位的土（`-` 表示移走的土）：\n\n```\n    * * *     -\n  * * * * *   - - -   -\n* * * * * * * * * * * *\n1 2 3 3 3 2 1 3 2 2 1 2\n```\n\n## Input\n\n第 $1$ 行输入整数 $n$ 和 $k$。\n\n之后 $n$ 行，每行输入一个整数，表示这块地的海拔。\n\n## Output\n\n如果仅能有 $k$ 个山顶至少要移走多少土。\n\n[samples]\n\n## Note\n\n对于 $100\\%$ 的数据，$1 \\leq n \\leq 10^3$，$1 \\leq k \\leq 25$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9835","tags":["2005","USACO"],"sample_group":[["12 1\n1\n2\n3\n3\n3\n2\n1\n3\n2\n2\n1\n2\n","5"]],"created_at":"2026-03-03 11:09:25"}}