2.0 KiB
2.0 KiB
区间2段覆盖
题目描述
有 n 个村庄坐落在数轴上，坐标为 $x[1...n]$。村庄之间有 n-1 条道路，其中有些道路是土路，有些是高速公路。具体地，第 i 个村庄和第 i+1 个村庄之间只有一条道路，要么是土路、要么是高速公路，并且输入会告诉所有 n-1 条道路的种类。
现在有 k(k\le 2) 个铺路计划，每个铺路计划可以在数轴上 任意选择一段长度$\le m$ 的区间 $[l,r]$，将其中间全部变成高速公路。注意区间端点可以任意选择，可以选在村庄处、村庄之间，甚至可以是小数。
请问该如何铺路，使得从 x[1] 走到 x[n] 路径上的土路总长度最小。
输入格式
第一行1个整数 $T$，代表有 T 组数据
每组数据第一行 3 个整数 n,k,m
第二行 n 个整数 $x[1,2,...,n]$，保证 x[1]=0, x[i-1]\le x[i]
第三行 1 个长度 n-1 的 01字符串，代表 n-1 条路的种类，0 代表高速公路，1 代表土路。
输出格式
输出 T 行，对于每组数据输出1个整数代表答案
自检样例
输入
1
2 1 2
2 3
0
输出
0
样例 #1
样例输入 #1
5
3 2 13
0 6 80
11
7 2 11
0 50 80 83 86 97 97
111011
2 2 43
0 83
1
9 2 47
0 26 34 40 71 75 79 98 99
11111101
10 2 36
0 14 28 29 30 37 55 64 65 81
011101000
样例输出 #1
54
72
0
1
0
样例 #2
样例输入 #2
2
5 2 3
0 1 2 3 5
1011
4 2 3
0 1 5 6
111
样例输出 #2
0
0
样例 #3
样例输入 #3
见下发样例
样例输出 #3
提示
对于100%的数据，1\le n\le 50000, 0\le m,x[i]\le 10^9,1\le T\le 100
subtask1(20pts)：n\le 500，m,x[i]\le 10^5，k=1
subtask2(20pts)：n\le 500，m,x[i]\le 10^5，k=2
subtask3(20pts)：n\le 50000，m,x[i]\le 10^9，k=1
subtask4(40pts)：n\le 50000，m,x[i]\le 10^9，k=2
【注意】请使用快速的读入方式