1. 题目
这道题大概的意思是说，一座城市中被埋了许多雷（用一个只含0和1的字符串表示城市，1代表有雷，0代表无雷）。
你作为一个排雷兵，需要花最少的钱引爆所有的雷来使城市中不再有雷（太逆天了，不知道是不是我理解错了，但总之就是要少花钱，还要引爆所有雷）。
当一个雷被引爆时，相邻的雷都会爆炸，所以你可以选择在没有雷的地方埋雷，使得两片雷区连起来，这样你就可以只花一次引爆需要的钱来引爆两片雷区。当然，埋雷也要花钱，不过在大多数案例中，埋雷的花费会较少。
输入
第一行输入一个整形t(1<=t<=100000)，表示接下来需要进行几轮排雷。
对于每一次排雷，第一行分别输入引爆雷和埋雷的花费(a和b, 且1<=a,b<=1000)，第二行输入一个只含0和1的字符串，表示城市中埋雷的情况。
对于每次测试，各轮排雷输入的字符串的总长度不会超过100000。
输出
依次输出每轮排雷的最低花费。
例如，题中所给的例子的第二轮排雷
引爆的花费是5，埋雷的花费是1
城市中雷的情况是01101110
于是选择将两片雷区连起来（在第四个位置上埋雷），再进行引爆，总花费是6。
2. 第一版解法
这一版并不完全算作第一版，其实是第二版。由于第一版老是通不过，于是我气急败坏地写了个暴力解法
2.1 思路
1. 最前端的0不需要考虑，因为在这这里埋雷毫无意义，于是先将字符串缩短一下，使得字符串以1开头。
2. 最后段其实也同样不需要考虑，但第一版的解法能够直接无视掉最后一段零（如果有的话）。
3. 除开这两段无需考虑的零，其他每一段零我们都需要考虑是否要埋雷来链接雷区。判断是否要埋雷的逻辑也很简单，因为链接一次雷区可以使我少引爆一次，所以就判断是埋雷花费高，还是多引爆一次花费高。
4. 在不考虑最后一段零的情况下，雷区数一定比零的段数多一，当每次决定不埋雷时，无雷区的数量加加，雷区数量就是无雷区数量加一。
5. 遍历字符串，用if语句来具体处理每一种情况。
2.2 代码
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main()
{
int n = 0;
scanf("%d", &n);
int* num = (int*)malloc(sizeof(int) * n);
for(int i = 0; i < n; i++)
{
int a = 0, b = 0, count = 0, j = 1, a_num = 1,b_num = 0, flag1 = 1, flag2 = 0;
char* ret = NULL;
char arr[100000] = {0};
scanf("%d%d", &a, &b);
getchar();
while((arr[0] = getchar()) == '0');
while((arr[j++] = getchar()) != '\n')
{
flag1 = 0;
}
if(flag1)
{
num[i] = 0;
continue;
}
for(int i = 1; i < j; i++)
{
if(arr[i] == '1'&&arr[i-1] == '0')//a数量加一，结算前方0
{
if(a <= b * count)
a_num++;
else
b_num = count;
count = 0;
}
else if(arr[i] == '1'&&arr[i-1] == '1')//连续一无意义
{;}
else if(arr[i] == '0'&&arr[i-1] == '1')//开始统计零
{
count++;
flag2 = 1;
}
else if(arr[i] == '0'&&arr[i-1] == '0'&&flag2)//连续零统计
{
count++;
}
}
if(a_num == 0)
{
num[i] = 0;
continue;
}
num[i] = a_num * a + b_num * b;
}
for(int i = 0; i < n; i++)
{
printf("%d\n", num[i]);
}
free(num);
return 0;
}2.3 总结
前面已经说了，这是一气之下写出来的破罐子破摔写法，没有什么参考意义。
经过这几天的做题，我发现，当你开始用if语句来处理各种特殊情况时，你就失败一半了。
3. 最终版解法
这一版才是严格意义上的第一版，只不过之前由于许多画蛇添足的操作导致程序老是通不过。后来上面那一版也过不了，我又回来继续改这一版，删掉了几句就过了。
3.1 思路
1. 这一版与上一版的不同在于，上一版采用的是依次遍历数组，用if语句逐个处理每个元素的方法；这一版采用了函数strtok。
2. 我们的目的其实就是找到两端都是1的无雷区，那么我们完全可以用strtok函数来将字符串分割出一个个的连续0段，然后判断是否要埋雷。
3. 这一次我们需要将尾端的无雷区也消减掉。
3.2 代码
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main()
{
int n = 0;
scanf("%d", &n);
int* num = (int*)malloc(sizeof(int) * n);
for(int i = 0; i < n; i++)
{
int a = 0, b = 0, count = 1, coin = 0, kong = 0, j = 0, flag1 = 1, flag2 = 1;
char* ret = NULL;
char arr[100006] = {0};
char* sep = "1";
scanf("%d%d", &a, &b);
getchar();
while((arr[j] = getchar()) != '\n')
{
if(arr[j] == '1')
flag1 = 0;
if(arr[j] == '0')
flag2 = 0;
j++;
}
if(flag1)
{
num[i] = 0;
continue;
}
if(flag2)
{
num[i] = a;
continue;
}
char* e = arr;
char* f = arr + j - 1;
while(*e == '0'&&e <= f){e++;};
while(*f == '0'&&e <= f){f--;};
*f = '\0';
for(ret = strtok(e, sep); ret != NULL; ret = strtok(NULL, sep))
{
int len = strlen(ret);
if(len*b < a)
{
coin += len*b;
}
else
{
kong++;
}
}
coin += (kong+1) * a;
num[i] = coin;
}
for(int i = 0; i < n; i++)
{
printf("%d\n", num[i]);
}
free(num);
return 0;
}3.3 总结
能用通用算法的，绝不用if语句来处理特使情况。
所以千万不要放弃一个较好的算法而去尝试暴力解法。
