← 返回题目

题库练习变换（change）

← 上一题下一题 →

A71643 | $变换（change）$

来源编程题

时间限制1s

内存限制512MB

通过 / 提交0/0

题目描述

游园会有有一个项目叫做变换，这个项目的规则如下： 现在有 S 和 T 两个长度相同的序列，都是由 0 和 1 构成。 我们想要把 S 序列变成 T 序列，每次变换我们可以把一个 0 变成 1，或者把一个 1 变成 0，第 i 个数改变一次所需要的代价是 Ci \times D，Ci 是题目给出的，跟位置 i 有关，即我们变换第 i 个数的时候使用，D 是当前 S 和 T 里面不匹配的数字的数量。 显然，不同的变换顺序的代价是不一样的。我们希望求出这个最小的变换代价。

输入格式

输入的第一行是一个整数 n ，表示序列的长度。 接下来一行有一个长度为 n 的序列，表示 S 序列，中间有一个空格隔开。 接下来一行有一个长度为 n 的序列，表示 T 序列，中间有一个空格隔开。 接下来一行有 n 个整数，表示 Ci ，整数用一个空格隔开。

输出格式

输出最小的变换代价。

输入输出样例

输入 #1

输出 #1

输入 #2

输出 #2

【输入输出样例 1 说明】 这里 S 和 T 是完全一样的，所以不需要变换，最小的变化代价是 0。 【输入输出样例 2 说明】 这里我们先变换第 1 个数， 花费的代价是 C_1 \times 3 = 3， 此时还有 3 个数没有匹配好， 所以乘 以 3， 然后我们变换第 2 个数， 花费的代价是 C_2 \times 2 = 4， 此时还有 2 个数没有匹配好， 所以乘 以 2， 然后我们变换第 3 个数， 花费的代价是 C_3 \times 1 = 3， 此时只有 1 个数没有匹配好， 所以乘 以 1， 总的代价 10， 为最小代价。 如果我们换种顺序去变换， 比如我们先变换第 3 个， 再变换第 2 个， 最后变换第 1 个， 那么花 费的代价就是 C_3 \times 3 + C_2 \times 2 + C_1 \times 1 = 14。 【数据范围】 对于所有的数据： 1 ≤ n ≤ 100000, 1 ≤ C_i ≤ 10000。 数据编号数据范围特殊性质1 \sim 3n ≤ 10保证 S 和 T 最多只有一个数不同4\sim 7n ≤ 20001 ≤ C_i ≤ 1008\sim 10n ≤ 10000无

C++ 编辑器

输入

输出