这题和hdu1003很相似，都是求的是区间的最大值，以及对应的区间，只不过这里的区间的值由R的数量和B的数量的差的绝对值决定，我一开始用的是统计区间的abs(numr-numb)来维护一个区间的值，但是最后写出来样例1没过，然后又换了种思路，我们要求的那个区间不是numr大于numb就是numb大于numr，对于第一种情况把r当作1，b当作-1，然后就用hdu1003的方法做，求出1到n区间的最大值和对应的区间，在这个区间里面r的数量-b的数量是1到n全部区间里的最大值，第二种情况同理。然后对求出的2个dp数组分别取maxx1，maxx2，取其中较大者，相等则取区间最靠左者。
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
const int maxn=1e5+10;
pii qj1[maxn],qj2[maxn];//记qj[i].first表示求出的以i位置结尾的区间的起点。second类似
int dp1[maxn],dp2[maxn];//dp[i]表示以i位置结尾的区间的最大值
string str;
int main()
{
int n;
cin>>str;
n=str.size();
str=" "+str;
dp1[0]=dp2[0]=0;
for(int i=1;i<=n;i++)//第一次dp把r视为1，b视为-1.
{
if(str[i]=='R')
{
if(dp1[i-1]+1>=1)
{
dp1[i]=dp1[i-1]+1;
qj1[i].first=qj1[i-1].first;
qj1[i].second=i;
if(i==1) qj1[i].first=i;
}
else
{
dp1[i]=1;
qj1[i].first=i;
qj1[i].second=i;
}
}
else
{
if(dp1[i-1]-1>=-1)
{
dp1[i]=dp1[i-1]-1;
qj1[i].first=qj1[i-1].first;
qj1[i].second=i;
if(i==1) qj1[i].first=i;
}
else
{
dp1[i]=-1;
qj1[i].first=i;
qj1[i].second=i;
}
}
}
for(int i=1;i<=n;i++)//第二次dp把r视为-1，b视为1.
{
if(str[i]=='B')
{
if(dp2[i-1]+1>=1)
{
dp2[i]=dp2[i-1]+1;
qj2[i].first=qj2[i-1].first;
qj2[i].second=i;
if(i==1) qj2[i].first=i;
}
else
{
dp2[i]=1;
qj2[i].first=i;
qj2[i].second=i;
}
}
else
{
if(dp2[i-1]-1>=-1)
{
dp2[i]=dp2[i-1]-1;
qj2[i].first=qj2[i-1].first;
qj2[i].second=i;
if(i==1) qj2[i].first=i;
}
else
{
dp2[i]=-1;
qj2[i].first=i;
qj2[i].second=i;
}
}
}
/*
cout<<"dp1:"<<endl;
for(int i=1;i<=n;i++)
cout<<dp1[i]<<" ";
cout<<endl;
cout<<"qj1:"<<endl;
for(int i=1;i<=n;i++)
cout<<qj1[i].first<<" "<<qj1[i].second<<endl;;
cout<<endl;
cout<<endl;
cout<<"dp2:"<<endl;
for(int i=1;i<=n;i++)
cout<<dp2[i]<<" ";
cout<<endl;
cout<<"qj2:"<<endl;
for(int i=1;i<=n;i++)
cout<<qj2[i].first<<" "<<qj2[i].second<<endl;;
cout<<endl;
*/
int low1,up1,low2,up2,maxx1=-1,maxx2=-1;
for(int i=1;i<=n;i++)
if(dp1[i]>maxx1)
{
maxx1=dp1[i];
low1=qj1[i].first;
up1=qj1[i].second;
}
for(int i=1;i<=n;i++)
if(dp2[i]>maxx2)
{
maxx2=dp2[i];
low2=qj2[i].first;
up2=qj2[i].second;
}
if(maxx1>maxx2)
cout<<low1<<" "<<up1<<endl;
else
if(maxx1<maxx2)
cout<<low2<<" "<<up2<<endl;
else
if(low1<low2)
cout<<low1<<" "<<up1<<endl;
else
cout<<low2<<" "<<up2<<endl;
return 0;
}