首页 > 代码库 > USACO Section1.1PROB Broken Necklace
USACO Section1.1PROB Broken Necklace
有点麻烦的一道模拟(官方题解好像有复杂度为$O(n)$DP的姿势?,感觉好烦,以后再细看~
在一些细节上调试了很久很久,囧RZ
/*ID: jusonal1PROG: beadsLANG: C++*/#include <iostream>#include <fstream>#include <string>#include <cstdio>#include <algorithm>#include <map>#include <cstring>using namespace std;char beads[1000];int n;int judge(int i) { if(i < 1) return n; else if(i > n) return 1; else return i;}int find_(int i) { int left = judge(i); int right = judge(i+1); int s_left = judge(i); int s_right = judge(i+1); int Left = judge(i); int Right = judge(i+1); int MAX = 0; while(beads[left] == beads[s_left]||beads[left] == ‘w‘) { ++MAX; if(beads[s_left] == ‘w‘) s_left = judge(--s_left); left = judge(--left); if(left == Right) return MAX+1; } while(beads[right] == beads[s_right]||beads[right] == ‘w‘) { ++MAX; if(beads[s_right] == ‘w‘) s_right = judge(++s_right); right = judge(++right); if(left == right) return MAX+1; } return MAX;}int main () { freopen("beads.in","r",stdin); freopen("beads.out","w",stdout); scanf("%d",&n); for(int i = 1;i <= n;++i) scanf(" %c",&beads[i]); int ans = 0; for(int i = 1;i <= n;++i) { ans = max(ans,find_(i)); } printf("%d\n",ans); return 0;}
USACO Section1.1PROB Broken Necklace
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。