[CCPC 2023 北京市赛] 史莱姆工厂

Luogu

IDLGP10041

Time1000ms

Memory512MB

DifficultyP7

动态规划 DP2023区间 DP省赛/邀请赛

有 $n$ 个史莱姆排成一行，其中第 $i$ 个的颜色为 $c_i$，质量为 $m_i$。你可以执行任意次把一个史莱姆的质量增加 $1$ 的操作，需要花费 $w$ 的价钱。但是一旦史莱姆的质量达到 $k$ 或以上，就会变得不稳定而必须在下一次操作之前被卖掉。你只能卖出质量大于等于 $k$ 的史莱姆。根据市场价，卖掉一个质量为 $i$ 的史莱姆可以得到 $p_i$ 的收入。保证 $p_i-p_{i-1}<w$。但不保证 $p_i$ 单调不降。卖掉一个史莱姆之后，它两边的史莱姆会被挤压继而靠在一起。如果这两个史莱姆颜色相同，那么就会互相融合成一个史莱姆，其质量是二者的质量之和。这个新的史莱姆也有可能需要被卖掉从而接着进行这个过程。你想知道卖掉所有史莱姆最多可以净赚多少。 ## Input 第一行三个正整数 $n,k,w(1\le n\le 150, 2\le k\le 10, 1\le w\le 10^6)$。第二行 $n$ 个正整数，其中第 $i$ 个表示 $c_i(1\le c_i\le n)$。保证 $c_i\not=c_{i-1}$。第三行 $n$ 个正整数，其中第 $i$ 个表示 $m_i(1\le m_i<k)$。第四行 $k-1$ 个整数，分别表示卖出质量为 $k$ 到 $2k-2$ 的史莱姆的收入，即 $p_k$ 到 $p_{2k-2}$，保证 $0\le p_i\le 10^9$，且 $p_i-p_{i-1}<w$。保证相邻两个史莱姆的颜色不同。 ## Output 一行一个整数，表示卖出所有史莱姆最大的净利润。 [samples] ## Note 先增加颜色为 $3$ 的史莱姆的质量。然后它被卖掉，获得 $5$ 的收入。然后增加颜色为 $1$ 的史莱姆的质量两次。然后它被卖掉，获得 $5$ 的收入。接着两个颜色为 $2$ 的史莱姆融合在一起卖掉，获得 $7$ 的收入。操作了三次需要 $18$ 的花费，所以净利润为 $-1$。可以证明不存在更好的方案。

Samples

Input #1

Output #1

-1

API Response (JSON)

{
  "problem": {
    "name": "[CCPC 2023 北京市赛] 史莱姆工厂",
    "description": {
      "content": "有 $n$ 个史莱姆排成一行，其中第 $i$ 个的颜色为 $c_i$，质量为 $m_i$。 你可以执行任意次把一个史莱姆的质量增加 $1$ 的操作，需要花费 $w$ 的价钱。 但是一旦史莱姆的质量达到 $k$ 或以上，就会变得不稳定而必须在下一次操作之前被卖掉。你只能卖出质量大于等于 $k$ 的史莱姆。根据市场价，卖掉一个质量为 $i$ 的史莱姆可以得到 $p_i$ 的收入。保证 $p_i-p",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P7"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10041"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "有 $n$ 个史莱姆排成一行，其中第 $i$ 个的颜色为 $c_i$，质量为 $m_i$。\n\n你可以执行任意次把一个史莱姆的质量增加 $1$ 的操作，需要花费 $w$ 的价钱。\n\n但是一旦史莱姆的质量达到 $k$ 或以上，就会变得不稳定而必须在下一次操作之前被卖掉。你只能卖出质量大于等于 $k$ 的史莱姆。根据市场价，卖掉一个质量为 $i$ 的史莱姆可以得到 $p_i$ 的收入。保证 $p_i-p...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments