Broken Necklace
题目大意：
有一串项链，有红色（r），白色（w），蓝色（b）组成，现在从任意位置把项链断开，从断开的两头分别向项链中间遍历。以左端为例，如果左端第一个为红色，那么从左开始取出所有红色，直到碰到蓝色停止。问最多可以从这串项链中取走多少珠子。（白色既可以当做红色，也可以当做蓝色）
解题思路：
O（N^2）
由于珠子数不多，最多350颗。那我们可以用纯暴力的方式暴搜，即从每一个可以拆开的地方断开项链，然后从两段遍历，得到一个值，并与当前最大值比较。
这里有一个技巧，把字符串复制一份连接到原先的后面，方便处理。
/*
ID: wuqi9395@126.com
PROG: beads
LANG: C++
*/
// O(n^2)
#include<iostream>
#include<fstream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<ctype.h>
#include<algorithm>
#include<string>
#define PI acos(-1.0)
#define maxn 1000
#define INF 1<<25
#define mem(a, b) memset(a, b, sizeof(a))
typedef long long ll;
using namespace std;
int main ()
{
string str;
int n, i, l, r, mx = 0;
ifstream fin ("beads.in");
ofstream fout ("beads.out");
fin>>n;
fin>>str;
str += str;
for (i = 0; i < n; i++)
{
l = r = 1;
int k = i + 1;
char flag;
while(l < n)
{
int j = i;
while(str[j] == 'w') j++;
flag = str[j];
if (str[k] == flag || str[k] == 'w') k++, l++;
else break;
}
k = i + n - 2;
while(r < n)
{
int j = i;
while(str[j] == 'w') j--;
flag = str[j];
if (str[k] == str[i + n - 1] || str[k] == 'w') k--, r++;
else break;
}
if (l + r > mx) mx = l + r;
}
if (mx > n) mx = n;
fout<<mx<<endl;
return 0;
}
O（N）
但如果N比较大，这种做法的效率就很低下，我们可以用DP的思想来解决这道题，状态方程如下：（用r 表示红色，b 表示蓝色）而且从断开出从左遍历和从右遍历一样
r[0] = p[0] = 0
If c = 'r' then r[p+1] = r[p] + 1 and b[p+1] = 0
because the length of the blue beads is 0.
if c = 'b' then b[p+1] = b[p] + 1 and r[p+1] = 0
if c = 'w' then both length of the red and length of blue beads
can be longer.
so r[p+1] = r[p]+1 and b[p+1] = b[p] + 1.
/*
ID: wuqi9395@126.com
PROG: beads
LANG: C++
*/
// O(N) DP
#include<iostream>
#include<fstream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<ctype.h>
#include<algorithm>
#include<string>
#define PI acos(-1.0)
#define maxn 1000
#define INF 1<<25
#define mem(a, b) memset(a, b, sizeof(a))
typedef long long ll;
using namespace std;
int main ()
{
ifstream fin ("beads.in");
ofstream fout ("beads.out");
int i, j, n, mx = 0;
int left[810][2] = {0}, right[810][2] = {0};
string str;
fin>>n>>str;
str += str;
for (i = 1; i <= 2 * n; i++)
{
if (str[i - 1] == 'r')
left[i][0] = left[i - 1][0] + 1, left[i][1] = 0;
else if (str[i - 1] == 'b')
left[i][1] = left[i - 1][1] + 1, left[i][0] = 0;
else
left[i][1] = left[i - 1][1] + 1, left[i][0] = left[i - 1][0] + 1;
}
for (i = 2 * n - 1; i >= 0; i--)
{
if (str[i] == 'r')
right[i][0] = right[i + 1][0] + 1, right[i][1] = 0;
else if (str[i] == 'b')
right[i][1] = right[i + 1][1] + 1, right[i][0] = 0;
else
right[i][1] = right[i + 1][1] + 1, right[i][0] = right[i + 1][0] + 1;
}
for (i = 0; i < 2 * n; i++)
mx = max(mx, max(left[i][0], left[i][1]) + max(right[i][0], right[i][1]));
mx = min(mx, n);
fout<<mx<<endl;
return 0;
}