<题目链接>
题目大意：
给你一段只由 'B'和'R'组成的字符串，问你在连续的区间内，"B"和"R"的差值最大是多少，输出该区间；如果对于差值相等的区间，优先输出左端点小的，左端点相同，优先输出右端点小的。
解题分析：
很明显要分两种情况讨论，一种是该区间内B比R多，第二种是该区间内R比B多。仔细思考后发现，可以将此题转化为最大连续和问题，对于B多的情况，用dp1来维护，将B看成1，R看成-1，对于R多的情况则用dp2来维护，将R看成1,B看成-1，然后就是用dp求解最大连续和即可，同时记录一下最大连续和所在的区间。
#include <bits/stdc++.h>
const int M = 1e5 + ;
#define INF 0x3f3f3f3f int main() {
char str[M];
scanf("%s", str + );
int len = strlen(str + );
int dpB[M], dpR[M];
for (int i = ; i <= len; i++) {
if (str[i] == 'B')
dpB[i] = ;
else
dpB[i] = -;
if (str[i] == 'R')
dpR[i] = ;
else
dpR[i] = -;
}
int s1, e1, s2, e2; //分别记录两种情况的最优区间
dpB[] = -, dpR[] = -;
int start1, start2, end1, end2;
int mx1 = -INF;
for (int i = ; i <= len; i++) { //先讨论B比R多的情况，求出B比R多的最大连续和
if (dpB[i - ] >= )
dpB[i] = dpB[i - ] + dpB[i];
else
s1 = i;
if (mx1 < dpB[i]) {
mx1 = dpB[i];
start1 = s1;
end1 = i;
}
}
int mx2 = -INF;
for (int i = ; i <= len; i++) { //讨论R比B多的情况，求出R比B多的最大连续和
if (dpR[i - ] >= )
dpR[i] = dpR[i - ] + dpR[i];
else
s2 = i;
if (mx2 < dpR[i]) {
mx2 = dpR[i];
start2 = s2;
end2 = i;
}
}
//然后就是比较两种情况的最大连续和,并且当最大连续和相同时，按题目要求格式输出
if (mx1 > mx2) {
printf("%d %d\n", start1, end1);
} else if (mx1 == mx2) {
if (start1 < start2)
printf("%d %d\n", start1, end1);
else if (start1 == start2) {
printf("%d ", start1);
end1 < end2 ? printf("%d\n", end1) : printf("%d\n", end2);
} else {
printf("%d %d\n", start2, end2);
}
} else {
printf("%d %d\n", start2, end2);
}
return ;
}
2018-09-17