【洛谷】P1203 [USACO1.1]坏掉的项链Broken Necklace

墨蓝 2022-09-09 02:19 137阅读 0赞

# 1. 前言 #

*  文章来源：CSDN@LawsonAbs
 *  这是一道经典的dp题，时限：20min
 *  注意边界条件

--------------------

# 2. 题目 #

## 2.1 [题目链接][Link 1] ##

## 2.2 题意 ##

给出一串由`r,b,w`字符组成的环形字符串，问如何从环中切割，拉直后，从左端和从右端分别找出最长的相同字符长度。其中`w`既可以做`r`字符，也可以代替`b`字符。

# 3. 分析 #

刷过题的都知道这是一道明眼的dp题。但是有如下几个问题需要注意：dp数组该如何定义？

*  定义`dpl[i] ,dpr[i]` 表示在第i个单词前分开，从左向右 和 从右向左可以划分得到的最大长度，然后最后合并求最大即可。i从0开始。有一个地方需要注意：dpl\[i\] 和 dpr\[i\] 都必须同时保持在单词前，或者同时在单词后分割。 我们这里选择在单词前分割，举个例子：

012345
    wrwrrb

当i=5时，分界情况就是：`wrwrr[分界点]b`，dpl\[i\] 的计算就是bwrwrr中的bw，长度为2（从分界点从左往右）；dpr\[5\]的长度就是`rrwrwb`为5（从分界点从右往左）；

*  因为像统一处理环形，所以我们将两个字符串拼接在一起。【其实如果不想拼接，应该可以用取模达到同样的效果】字符串拼接之后，最大的数组长度也需要改变为2\*maxN。

# 4. 代码 #

代码无非就是这些分界点比较难搞，如果这些搞清楚之后，就很好的写代码了。

#include<iostream>
    #include<string>
    
    using namespace std;
    const  int maxN = 400;
    /* */
    int main(){ 
    	int dpl[maxN],dpr[maxN];
    	int n ;
    	string str;
    	//cin >> n ;
    	cin >> str;
    	str += str; // 两份拼凑
    	//初始化都为1 
    	fill(dpl,dpl+maxN,1);
    	fill(dpr,dpr+maxN,1);
    	char cur_color;
    	int len = str.length();	
    	//dpl[i]表示从第i个节点前分开 
    	for (int i = 0;i< len-1;i++){ 
    		cur_color = str[i];
    		for(int j = i+1;j<len;j++){ //直接取模 
    			if(cur_color == str[j] || str[j] == 'w'){ 
    				dpl[i]++;				
    			}
    			else if(cur_color == 'w' && str[j]!='w'){ 
    				cur_color = str[j] ;  //修改当前色 
    				dpl[i]++;
    			}				
    			else //跳出循环，结束 
    				break;			
    		}
    	}
    	//从右往左 dpr[i] 必须包括自己 ，dpr[i]表示从第i个节点前分开 
    	for (int i = len-1;i >=1 ;i--){ 
    		cur_color = str[i-1]; 
    		for(int j = i-2;j>=0;j--){ 			
    			if(cur_color == str[j] || str[j] == 'w' ){ 
    				dpr[i]++;				
    			}
    			else if(cur_color == 'w' && str[j]!='w'){ 
    				cur_color = str[j] ;  //修改当前色 
    				dpr[i]++;	
    			}				
    			else //跳出循环，结束 
    				break;  
    		}
    	}
    	
    	
    	int res = 0;
    	for (int i = 0;i< len;i++){ 
    		//cout <<"i="<<i<<" "<< dpl[i] <<" "<< dpr[i]<<"\n";
    		res = max(dpl[i]+dpr[i],res);
    	}
    	//需要注意最长不过原始str 本身的长度 
    	cout << min(res,len/2) ;
    } 
    /* 1 b 3 rrr 5 wrwrr 29 brbrrrbbbrrrrrbrrbbrbbbbrrrrb 29 wwwbbrwrbrbrrbrbrwrwwrbwrwrrb */

[Link 1]: https://www.luogu.com.cn/problem/P1203