本文主要是介绍九度OJ 1260：珍珠项链 （字符串处理、DP），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
- 题目描述：
-
假设有一条珍珠项链，有很多珍珠，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 100000void 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\n", 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;elsea[i] = 2;//printf("%d", a[i]);}//printf("\n");for (k=0; k<2; k++){int towards = k*2 - 1;count(c[k], a, n, 0, towards);//printf("c[%d][%d]=%d,%d\n", 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\n", 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\n", max);} return 0;
}
/**************************************************************Problem: 1260User: liangrx06Language: CResult: AcceptedTime:210 msMemory:2896 kb
****************************************************************/这篇关于九度OJ 1260：珍珠项链 （字符串处理、DP）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
