[蓝桥杯][算法提高VIP]项链（dfs）

题目描述
由 n(1≤n≤100)　　个珠子组成的一个项链，珠子有红、蓝、白三种颜色，各种颜色的珠子的安排顺序由键盘输入的字符串任意给定。蓝色用小写字母b表示,红色用小写字母r表示,　　白色用小写字母w表示.

假定从项链的某处将其剪断，把它摆成一条直线。先从左端向右收集同色珠子，遇到第一个异色珠子时停止.　　收集过程中, 白色是一种特殊颜色, 既可以看成红色也可以看成蓝色。然后再从剩余珠子的右端向左重复上述过程。

例如：对下图一所示的项链, 如果从图一中标记的位置0处剪断,　　则按顺时针顺序得到wbbbwwrrbwbrrwb（如图二所示）。这时从左端开始收集可以得到wbbbww,　　 共6个珠子；然后从剩余珠子右端开始收集得到wb，共2个珠子。这种剪法共可收集到6+2=8个珠子。 如果从图一中标记的位置4处剪断,　　则按顺时针顺序得到wwrrbwbrrwbwbbb（如图二所示）。这时从左端收集可以得到wwrr,共4个珠子； 然后从剩余珠子右端收集可以得到wbwbbb，共6个珠子。这种剪法共可收集到4+6=10个珠子。

要求: 在项链中选择合适的剪断位置, 使得从左右两端收集到的珠子数目之和最大，输出收集到的珠子数的最大值M。

输入
由小写字母b,r,w组成的字符串。此字符串记录了一个首尾相接的项链从某处断开后，按顺时针顺序得到的珠子的直线排列。
输出
收集到的珠子数的最大值 M
样例输入
wbbbwwrrbwbrrwb
样例输出
10
思路：我们对于每一个节点，分别向左向右延伸。这个节点所延伸的长度就是这个节点所能扩展的长度。如果这个节点不是‘W’的话，扩展之后就不用再次扩展了。如果是‘W’的话，就需要再次扩展，因为这次扩展有可能比上一次扩展更优。
代码如下：

#include<bits/stdc++.h> #define LL long long using namespace std;const int maxx=1e2+100; int l[maxx],r[maxx]; string s;inline int dfs(int ll[],int i,int dir,char c,int num) {if(s[i]!=c&&s[i]!='w'&&c!='w') return 0;if(num>s.length()) return s.length();int sum=1;int ti;if(i+dir==s.length()) ti=0;else if(i+dir<0) ti=s.length()-1;else ti=i+dir;if(c=='w'){if(s[ti]=='w') sum+=dfs(ll,ti,dir,c,num+1);else sum+=dfs(ll,ti,dir,s[ti],num+1);}else sum+=dfs(ll,ti,dir,c,num+1);ll[i]=max(min((int)s.length(),sum),ll[i]);return min(sum,(int)s.length()); } int main() {cin>>s;int len=s.length();memset(l,0,sizeof(l));memset(r,0,sizeof(r));for(int i=0;i<s.length();i++){if(l[i]&&s[i]!='w') continue;dfs(l,i,1,s[i],1);}for(int i=s.length()-1;i>=0;i--){if(r[i]&&s[i]!='w') continue;dfs(r,i,-1,s[i],1);}int _max=0;for(int i=0;i<s.length();i++){_max=max(_max,l[i]+r[i-1<0?s.length()-1:i-1]);}cout<<min(_max,(int)(s.length()))<<endl;//和字符串长度取最小值。return 0; }

努力加油a啊，(^o)/~

总结

以上是生活随笔为你收集整理的[蓝桥杯][算法提高VIP]项链（dfs）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。