{"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_{i-1}<w$。但不保证 $p_i$ 单调不降。\n\n卖掉一个史莱姆之后，它两边的史莱姆会被挤压继而靠在一起。如果这两个史莱姆颜色相同，那么就会互相融合成一个史莱姆，其质量是二者的质量之和。这个新的史莱姆也有可能需要被卖掉从而接着进行这个过程。\n\n你想知道卖掉所有史莱姆最多可以净赚多少。\n\n## Input\n\n第一行三个正整数 $n,k,w(1\\le n\\le 150, 2\\le k\\le 10, 1\\le w\\le 10^6)$。\n\n第二行 $n$ 个正整数，其中第 $i$ 个表示 $c_i(1\\le c_i\\le n)$。保证 $c_i\\not=c_{i-1}$。\n\n第三行 $n$ 个正整数，其中第 $i$ 个表示 $m_i(1\\le m_i<k)$。\n\n第四行 $k-1$ 个整数，分别表示卖出质量为 $k$ 到 $2k-2$ 的史莱姆的收入，即 $p_k$ 到 $p_{2k-2}$，保证 $0\\le p_i\\le 10^9$，且 $p_i-p_{i-1}<w$。\n\n保证相邻两个史莱姆的颜色不同。\n\n## Output\n\n一行一个整数，表示卖出所有史莱姆最大的净利润。\n\n[samples]\n\n## Note\n\n先增加颜色为 $3$ 的史莱姆的质量。然后它被卖掉，获得 $5$ 的收入。\n\n然后增加颜色为 $1$ 的史莱姆的质量两次。然后它被卖掉，获得 $5$ 的收入。接着两个颜色为 $2$ 的史莱姆融合在一起卖掉，获得 $7$ 的收入。\n\n操作了三次需要 $18$ 的花费，所以净利润为 $-1$。可以证明不存在更好的方案。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10041","tags":["动态规划 DP","2023","区间 DP","省赛/邀请赛"],"sample_group":[["4 5 6\n2 1 2 3\n3 3 3 4\n5 7 9 11","-1"]],"created_at":"2026-03-03 11:09:25"}}