C

其实本来这题是放在 B 题之前的，看题目名称就知道。

可是考虑到种种原因，看上去这道题场切的人会比上一题少，所以就商量着把这道题放在 C 上来了。

考虑到 $n\le 3000n\backslash le3000$，我们可以给出一个 $O(n^2)O(n^2)$ 的算法。

首先预处理一下区间 min，一会方便计算。

然后考虑枚举 $kk$，表示初始为 $00$ 的数 $SS$ 的前 $kk$ 位通过 $\times 2\backslash times2$ 变换得到，后面 $n-kn-k$ 位通过直接修改得到。

然后就通过区间 min 来决定在哪一次 $\times 2\backslash times2$ 操作之前修改一个对应位就可以了。

稍微说明一下上面的过程为什么是对的：

• 考虑最后的数 $VV$ 的第 $ii$ 位怎么得到：

  1. 方案一：在“再也不执行”$\times 2\backslash times2$ 操作的时候花费 $a_{i}a\_i$ 得到；
  2. 方案二：在某个位置 $jj$，花费 $a_{j}a\_j$ 得到一个 1，然后 $\times 2\backslash times2$ 操作执行 $i-ji-j$ 次，把第 $jj$ 位的 1 挪到第 $ii$ 位上来。

方案一好算，直接求前缀和就好了；方案二其实也好算，本质上就是知道了我这一位肯定要通过 $\times 2\backslash times2$ 操作得到，那我看看执行几次 $\times 2\backslash times2$ 操作得到不就好了么？

这题数据范围出小了，很明显区间取 min 和后面类似 dp 的过程可以优化到 $O(n\log n)O(n\backslash log\; n)$，在此不再赘述。

（另外我不知道为什么出题人把这个 $bb$ 的值给的这么小）

#include<cstdio>
#define int long long
int init(){
	char c = getchar();
	int x = 0, f = 1;
	for (; c < '0' || c > '9'; c = getchar())
		if (c == '-') f = -1;
	for (; c >= '0' && c <= '9'; c = getchar())
		x = (x << 1) + (x << 3) + (c ^ 48);
	return x * f;
}
void print(int x){
	if (x < 0) x = -x, putchar('-');
	if (x > 9) print(x / 10);
	putchar(x % 10 + '0');
}
const int N = (int) 3e3 + 5;
int a[N], c[N], min[N][N];
int mn(int x, int y){
	return x < y ? x : y;
}
signed main(){
	int n = init();
	for (int i = 1; i <= n; ++i)
		a[i] = init();
	int b = init();
	for (int i = 1; i <= n; ++i) {
		while (c[i] < '0' || c[i] > '1')
			c[i] = getchar();
		c[i] -= '0';
	}
	for (int i = 1; i <= n; ++i)
		for (int j = i; j <= n; ++j)
			if (i < j) min[i][j] = mn(min[i][j - 1], a[j]);
			else min[i][j] = a[j];
	int ans = (int) 1e18;
	for (int k = 0; k < n; ++k) {
		int cnt = b * k;
		for (int i = 1; i <= n; ++i)
			if (c[i]) cnt += min[i - k < 1 ? 1 : i - k][i];
		ans = cnt < ans ? cnt : ans;
	}
	print(ans), putchar('\n');
}