- 题目描述：
-
假设有一条珍珠项链，有很多珍珠，r代表红色， b代表蓝色， w代表白色。
假设你在某一处剪开之后，你会沿着顺时针和逆时针方向收集珠子，但是收集珠子有一个条件：
1.只能收集同一种颜色的珠子 2.w可以表示红色也可以表示蓝色。
你怎么剪才能收集到尽可能多的珠子。
例如下图中，在2、3之间剪开，逆时针方向可以收集到3颗珠子（r），顺时针方向能收集到3颗珠子(b)，这样2、3之间剪开能收集6颗
12
rr
10 w w 3
9 b b 4
8 w w 5
rr
76
- 输入：
-
输入包含一个仅有'r','w','b'三个字符的字符串。
- 输出：
-
可能有多组测试数据，对于每组数据，
输出最多可以收集多少颗珍珠。
- 样例输入：
-
rrwbwrrwbw
- 样例输出：
-
6
思路：
此题相较于一般的DP，麻烦之处是字符串构成一个圆。因此不是从1到n的DP，而是从第1个n到第n个n的递归。
代码比较晦涩，只因我一时手贱非要写成两个方向统一的函数代码。
代码：
#include <stdio.h>
#include <string.h>
#define N 100000
void count(int c[N][2], int a[N], int n, int begin, int towards)
{
int i = begin;
while (i != begin + n*towards && a[(i+n)%n] == 2)
i += towards;
//printf("begin=%d, i=%d, towards=%d
", begin, i, towards);
c[begin][0] = c[begin][1] = (i - begin)*towards;
if (i != begin + n*towards)
{
int color = a[(i+n)%n];
i += towards;
while (i != begin + n*towards && a[(i+n)%n] != 1-color)
i += towards;
c[begin][color] = (i - begin)*towards;
}
}
void dp(int c[N][2], int a[N], int n, int i, int j)
{
int color = a[i];
if (color == 2)
{
c[i][0] = (c[j][0] < n) ? (c[j][0] + 1) : n;
c[i][1] = (c[j][1] < n) ? (c[j][1] + 1) : n;
}
else
{
c[i][color] = c[j][color] + 1;
c[i][1-color] = 0;
}
}
int Max(int x, int y)
{
return (x > y) ? x : y;
}
int main(void)
{
int n, i, j, k;
char s[N+1];
int a[N];
int c[2][N][2];
while (scanf("%s", s) != EOF)
{
n = strlen(s);
for (i=0; i<n; i++)
{
if (s[i] == 'r')
a[i] = 0;
else if (s[i] == 'b')
a[i] = 1;
else
a[i] = 2;
//printf("%d", a[i]);
}
//printf("
");
for (k=0; k<2; k++)
{
int towards = k*2 - 1;
count(c[k], a, n, 0, towards);
//printf("c[%d][%d]=%d,%d
", k, 0, c[k][0][0], c[k][0][1]);
for (i=-towards; i!=-(n*towards); i-=towards)
{
j = (i+towards+n)%n;
int ii = (i+n)%n;
dp(c[k], a, n, ii, j);
//printf("c[%d][%d]=%d,%d
", k, ii, c[k][ii][0], c[k][ii][1]);
}
}
int max = 0;
for (i=0; i<n; i++)
{
int t1 = Max(c[0][i][0], c[0][i][1]);
j = (i+1)%n;
int t2 = Max(c[1][j][0], c[1][j][1]);
max = (t1+t2 > max) ? t1+t2 : max;
if (max >= n)
{
max = n;
break;
}
}
printf("%d
", max);
}
return 0;
}
/**************************************************************
Problem: 1260
User: liangrx06
Language: C
Result: Accepted
Time:210 ms
Memory:2896 kb
****************************************************************/