洛谷P1203 坏掉的项链

2023-03-13,,

洛谷P1203 坏掉项链

首先看到这题的数据样例,3<=n<=350,不是水水暴搜就过了嘛

不难想到暴力解,先破环成链

因为可能有全部都可换成一种颜色的情况,考虑每次遇到s[i]==s[i+1]的情况,直接跳过,

如果最后结局ans仍为初始值(推荐-1),直接输出项链大小n,否则判断当前节点是否为white,如果是white就赋值一种颜色,左右暴搜,如果暴搜过程中发现得到的值比n还要大,直接返回n,然后赋值另一种继续搜,每次ans=max{ans, check(i)},最后赋值回white,然后就A了,很水的题对吧

下面贴一下核心代码

int check(int x){
int ans=0;
char c2 = a[x+1],c1=a[x];
for(int i=x;;i--){
if(a[i]==c1)ans++;
else if(a[i]=='w')ans++;
else break;
if(ans >= n)return n;
}
for(int i=x+1;;i++){
if(a[i]==c2)ans++;
else if(a[i]=='w')ans++;
else break;
if(ans >= n)return n;
}
return ans;
}

真的,好困,,好困(゚Д゚≡゚Д゚)谁在说话?

洛谷P1203 坏掉的项链的相关教程结束。

《洛谷P1203 坏掉的项链.doc》

下载本文的Word格式文档,以方便收藏与打印。