[USACO05OPEN] Landscaping G

Luogu

IDLGP9835

Time500ms

Memory64MB

DifficultyP4

2005USACO

农夫约翰正在做一次艰难的转型，从养山羊改成养奶牛，他的农场，由于是为养山羊而设计的所以有太多的山，为了养牛就必须将它整平。但是，将山整平是件很花钱的工作，所以他要移走尽可能少的土。由于农场很细长，所以可以用一个 $n$ 和 $n$ 个整数（范围 $[1,10^6]$）组成的二维的数组来表示，如： ``` 1 2 3 3 3 2 1 3 2 2 1 2 ``` 上述农场的侧面图是这样的： ``` * * * * * * * * * * * * * * * * * * * * * * * * * 1 2 3 3 3 2 1 3 2 2 1 2 ``` 一个或是一些连续等高的地面，如果它左边与右边的海拔都比它低的话，就被称为山顶，上面的例子就有三个山顶。确定如果要使地图上仅有 $k$ 个山顶，至少要移走多少体积的土（每块地面减少一单位海拔需移走一单位的土）。注意，地面的海拔只能被降低不能被升高。对于例子，如果要减少到只有 $1$ 个山顶，这需要移走 $2+1+1+1=5$ 个单位的土（`-` 表示移走的土）： ``` * * * - * * * * * - - - - * * * * * * * * * * * * 1 2 3 3 3 2 1 3 2 2 1 2 ``` ## Input 第 $1$ 行输入整数 $n$ 和 $k$。之后 $n$ 行，每行输入一个整数，表示这块地的海拔。 ## Output 如果仅能有 $k$ 个山顶至少要移走多少土。 [samples] ## Note 对于 $100\%$ 的数据，$1 \leq n \leq 10^3$，$1 \leq k \leq 25$。

Samples

Input #1

Output #1

API Response (JSON)

{
  "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...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments