首页 > 代码库 > USACO Broken Necklace
USACO Broken Necklace
这么个所谓简单的题目弄了一下午加一晚上，呵呵，怎么也算不对。
一定会有一个简单的方法。
晚上去新都回来后，又坐在电脑面前思索这个问题。
多次删除写出的眼看就要成功的代码，因为不够简洁。
突然顿悟：
1.串相联；
假设数数当前位置为pos;
2.k[pos]==‘w‘，不可能是最大。
3.k[pos+1]==‘w‘,不可能是最大。
4.k[pos]=k[pos+1],不可能是最大。
5.pos==0,不能往左数。
所以，
6.只有k[pos]!=k[pos+1]才有可能数出最大：
即‘r‘,‘b‘,或‘b‘,‘r‘这种组合才可能最大。
所以，最后的算法是，找到合适的pos,
从pos往左数＋从pos+1往右数这些组合，找出最大的，呵呵！
/*ID: qq104801LANG: CTASK: beads.c*/#include <stdio.h>#include <stdlib.h>#include <string.h>/* for debug only:counter*/void debug_dummy(void){ return;}int n;char k[600];int count(int pos){ int index=0; int l=1,r=1; if (k[pos]==‘w‘ || k[pos+1]==‘w‘ || k[pos]==k[pos+1] || pos<1) return 1; index=pos; while(--index && index>=0) { if ((k[index]==k[pos]) || (k[index]==‘w‘)) l++; else break; } index=pos+1; while(++index && k[index]!=‘\0‘) { if ((k[index]==k[pos+1]) || (k[index]==‘w‘)) r++; else break; } //printf("pos:%d l:%d r:%d l+r:%d\n",pos,l,r,l+r); return l+r;}void init(){ int i; int cc=0; char c1,c2; c1=‘\0‘; i=n-1; while(i++) { cc++; k[i]=k[i-n]; if (k[i]!=k[0]) { c1=k[i]; } if (c1!=‘\0‘ && k[i]!=c1) break; } k[++i]=‘\0‘; //printf("cc;%d\n",cc); //printf("k:%s\n",k);}main () { FILE *fin = fopen ("beads.in", "r"); FILE *fout = fopen ("beads.out", "w"); fscanf(fin,"%d",&n); fscanf(fin,"%s",&k); //printf("n:%d\n",n); //printf("k:%s\n",k); init(); int i; int max,t; t=0; max=0; for(i=0;i<n;i++) { t=count(i); if (max<t) max=t; } //printf("max:%d\n",max); fprintf(fout,"%d\n",max); fclose(fin); fclose(fout); exit (0);}
USACO Broken Necklace
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。