断项链USACO问题
破碎的项链
你有一条N红色，白色或蓝色珠子项链（3 <= N <= 350），其中一些是红色，另一些是蓝色，其他是白色，随意排列。 以下是n = 29的两个示例：
1 2 1 2 rbbrbrrb rbbb rrbr rrwr brww bbrr bbbb bbrb rrbr brrr brrr rrrb rbrrrw Figure A Figure B r red bead b blue bead w white bead 在下面的文本中考虑第一和第二的珠子已在图片中标出。
图A中的配置可以表示为b和r的串，其中b表示蓝色珠子，r表示红色珠子，如下所示：brbrrrbbbrrrrrbrrbbrbbbbrrrrb。
假设你要在某个时候打破项链，直接铺设，然后从一端收集相同颜色的珠子，直到你到达不同颜色的珠子，并为另一端做同样的事情（可能不是与此之前收集的珠子颜色相同的颜色）。
确定项链应该被打破的点，以便可以收集大量的珠子。
例
例如，对于图A中的项链，可以收集8个珠子，其中断裂点在珠子9和珠子10之间或者在珠子24和珠子25之间。
在一些项链中，包括白色珠子，如上面的图B所示。 收集珠子时，遇到的白色珠子可以被视为红色或蓝色，然后涂上所需的颜色。 表示此配置的字符串将包含三个符号r，b和w。
这是USACO训练问题，我遇到了麻烦; 我一直得到错误的答案。 …请不要告诉我这是愚蠢的或愚蠢的; 这没有帮助！ ：d
嘿，我很喜欢这个，但我没有费心去编码。 无论如何，我的想法是这样的。
首先，您不需要存储所有珠子颜色（Go Australian拼写！），您只需要存储多少相同颜色的珠子。 因此对于：
RRBBBWRR
你只需要存储：
2R 3B 1W 2R
有一点需要注意的是，如果结尾和起始珠子是相同的颜色，你必须考虑到这一点，所以
RRBBBRR
应该存储为
4R 3B or 3B 4R
一样。 请注意，这样做的原因不是为了节省内存或任何东西，而是为了确保彼此相邻的珠子是不同的颜色。 我们通过组合相同颜色的珠子来做到这一点。
接下来你要经历每一个：
– 如果它是红色的，你将之后的所有颜色相加，直到找到蓝色，然后继续添加，直到找到另一个红色
– 如果是蓝色，除了相反之外，做同样的事情
– 如果是白色，那么下一个珠子将是红色或蓝色。 除了添加白色珠子的数量外，如上所述
这里有些例子。 序列开始和结束的标记。
B|RB|R
我们找到一个R然后是一个B然后是另一个R.所以我们必须停在B处
B|RWRB|R
我们找到一个R，然后是另一个R，但我们还没有找到B，所以我们继续。 然后我们找到一个B然后找到另一个R.这一次，因为我们找到了一个B，我们必须停下来。
B|RBW|R
我们找到一个R然后是B但我们可以继续，因为下一个是W，然后我们找到另一个R所以我们必须停止。 在
B|WRBWB|R
我们计算W然后我们找到一个R.因此我们继续直到找到一个B然后继续直到找到另一个R.这个
B|WBRWR|B
是一个相反的情况。
现在你所要做的就是实现它：D。 当然，这没有考虑R，B和W中珠子的实际数量，并且仅是单珠子序列的实例。 您必须检查所有可能的序列。 你还必须处理从背面到开始环绕的序列。
最后，您可能会注意到此算法有时会浪费但N <350，因此即使O（N ^ 3）也应该在1秒内工作。 也许2.无论如何，我相信这是O（N ^ 2）所以你应该能够在一秒钟内运行这个程序350次。 请评论是否有些令人困惑，因为我不是最好的解释者。 快乐的编码。
#include #include #include int main(){ int numBeads; char temp1[705]; char temp2[705]; int i,j,k,lim; int count1 = 0; int count2 = 0; int maxcount1 = 0; char virgin = ' '; bool flag = false; //flag == true if virgin doesn't match FILE* fin = fopen("beads.in","r"); FILE* fout = fopen("beads.out","w"); fscanf(fin,"%d",&numBeads); fscanf(fin,"%s",temp1); strcpy(temp2,temp1); strcat(temp1,temp2); for(i=0,j=numBeads-1;i=lim;k--){ if(temp1[k]=='w'){ count2++; } else if(temp1[k]=='r'){ if(virgin==' '){ virgin = 'r'; } if(virgin=='r') count2++; else{ flag = true; k--; } } else if(temp1[k]=='b'){ if(virgin==' '){ virgin = 'b'; } if(virgin=='b') count2++; else{ flag = true; k--; } } } if(maxcount1 < (count1+ count2))maxcount1 = count1 + count2; } fprintf(fout,"%d\n",maxcount1); return 0; }
这是我的代码：
import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.FileReader; import java.io.FileWriter; import java.io.PrintWriter; /** * * @author Bansari */ public class beads { public static void main(String args[]){ try{ BufferedReader f = new BufferedReader(new FileReader("beads.in")); // input file name goes above PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter("str.txt"))); int len = Integer.parseInt(f.readLine()); String s=f.readLine(); int c1=0,c2=0; int breakpoint=0; int max = 0; for(int i = 1;i<=len;i++){ char before = s.charAt((i-1)%len); char after = s.charAt(i%len); if(before != after){ c1=0; c2=0; int index = i-1; while(s.charAt(index)==before || s.charAt(index)=='w'){ char sc = s.charAt(index); c1++; if(index==0) index = len-1; else index--; } index = i; while(s.charAt(index%len)==after || s.charAt(index%len)=='w'){ c2++; if(index == len-1) index = 0; else index++; } if(max < (c1 + c2)){ breakpoint=i; max = c1+c2; } } } out.println(max); out.close(); System.exit(0); }catch(Exception e){ } } }
当你在计算竞赛中遇到一个奇怪的问题时，它很可能是动态编程 （Bellman类，而不是Ruby类）。
看看这个教程 。
动态编程的基本思想是通过回答小的子问题来建立一个“大”的答案。 我的第一个直觉思想是考虑更长和更长的项链，从一个珠子开始，但我真的不是特别擅长动态编程问题。 （我也注意到在现实世界中遇到DP问题最常见的地方是计算奥林匹克运动员和计算机科学课程中的问题集。）
被收回 – 这是错的，因为它不考虑白色珠子。
我可以看到比接受的答案更简单，或者解释过于复杂。 这是伪代码中的算法（忽略所有相同颜色的情况）：
p = position of first bead of different color than bead 0 create array of run-lengths: r={5,15,2,9,13} create array of sums of adjacents s={20,17,11,22,18} (wrap last) find index, k, in s[] of max sum: here it is s[3] position = p + r[0] + r[1] + ... + r[k]
很长一段时间我在学习编程的时候做过这个。 我只是搜索了我的电脑，找到了我提交的解决方案。 我可以提供代码，但一切都搞砸了。 = P
import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.FileNotFoundException; import java.io.FileReader; import java.io.FileWriter; import java.io.PrintWriter; public class beads { /** * @param args * @throws Exception */ public static void main(String[] args) throws Exception { // TODO Auto-generated method stub new beads().go(); } private void go() throws Exception { // TODO Auto-generated method stub BufferedReader bin = new BufferedReader(new FileReader("beads.in")); PrintWriter pout = new PrintWriter(new BufferedWriter(new FileWriter("beads.out"))); int count = Integer.parseInt(bin.readLine()); String beads = bin.readLine(); int ans = compute(beads); pout.println(ans); pout.close(); } private int compute(String beads) { // TODO Auto-generated method stub int length = beads.length(); int maxbeads = 0; for(int i = 0; i < length; i++){ int left = 0; int right = 0; left = computeLeft(beads,i); if(left == length){ maxbeads = left; break;} right = computeRigtht(beads,i); if(right == length){ maxbeads = right; break;} if((left+right) > maxbeads) maxbeads = left+right; if(maxbeads == length) break; } return maxbeads; } private int computeLeft(String beads, int i) { // TODO Auto-generated method stub int l = beads.length(); int j = i; int count = 0; char ch = beads.charAt(i); for(; j >=0; j--){ if(ch == 'w'){//Didnt notice this kind of case before ch = beads.charAt(j); count++; } else if(beads.charAt(j) == ch || beads.charAt(j)== 'w'){ count++; } else break; } if(j < 0) j = l-1; for(; j > i; j--){ if(beads.charAt(j) == ch || beads.charAt(j)== 'w'){ count++; } else break; } return count; } private int computeRigtht(String beads, int i) { // TODO Auto-generated method stub int l = beads.length(); int j = 0; if(i == l-1) j = 0; else j = i+1; int k = j; int count = 0; int ch = beads.charAt(j); for(; j
}
我使用了quasiverse的算法并解决了它。 USACO服务器已关闭，我无法对他们的判断进行测试，但我想我已经解决了。
#include #include #include #include #include #define MAXLEN 350 using namespace std; ofstream fout ("beads.out"); typedef struct node { char color; int times; int lenMax; struct node* next; } nodeList; nodeList * getnode() { nodeList* temp=(nodeList*) malloc (sizeof(nodeList)); temp->next=NULL; temp->lenMax=0; return temp; } void append(nodeList **head,char tColor,int m) { nodeList *p=NULL,*newNode=NULL; newNode =getnode(); newNode->color=tColor; newNode->times=m; newNode->lenMax=0; if(*head==NULL) { *head=newNode; return; } p=*head; while(p->next) p=p->next; p->next=newNode; } void shiftNodes(nodeList **head) { int mon=0; nodeList *last=NULL,*p=NULL,*t=NULL; p=*head; do { //cout<color<<" "<times<next; } while(p!=NULL); p=*head; last->next=*head; t=*head; do { if(((*head)->color=='w' || (last)->color=='w' ) || (*head)->color==last->color) { (*head)=(*head)->next; last=last->next; } else if((*head)->color!=last->color ) { break; } p=p->next; } while(p!=t); } void computeLenMaxB(nodeList ** head) { nodeList *p =NULL,*t=NULL,*s=NULL; t=p=*head; bool gotR=false; int tempLenMax=0; do { if(p->color=='b' && gotR){ break; } else if(p->color=='b' && !gotR){ tempLenMax+=p->times; } else if(p->color=='r' && !gotR){ tempLenMax+=p->times; gotR=true; } else if(p->color=='r' && gotR){ tempLenMax+=p->times; } else if(p->color=='w' ){ tempLenMax+=p->times; } p=p->next; } while(p!=t); (*head)->lenMax=tempLenMax; } void computeLenMaxR(nodeList ** head) { nodeList *p =NULL,*t=NULL,*s=NULL; t=p=*head; bool gotR=false; int tempLenMax=0; do { if(p->color=='r' && gotR){ break; } else if(p->color=='r' && !gotR){ tempLenMax+=p->times; } else if(p->color=='b' && !gotR){ tempLenMax+=p->times; gotR=true; } else if(p->color=='b' && gotR){ tempLenMax+=p->times; } else if(p->color=='w' ){ tempLenMax+=p->times; } p=p->next; } while(p!=t); (*head)->lenMax=tempLenMax; } void fillLenMax(nodeList ** head) { nodeList *p =NULL,*t=NULL,*s=NULL; t=p=*head; int wBeads=0; do { s=p; if(p->color=='b') { computeLenMaxB(&p); } else if(p->color=='r') { computeLenMaxR(&p); } else if(p->color=='w') { if(p->next->color=='b'){ computeLenMaxB(&p); } else if(p->next->color=='r'){ computeLenMaxR(&p); } } p=p->next; } while(p!=t); } int calcMaxLenMax(nodeList *head) { nodeList *p=NULL; p=head; int max=0; do { //fout<color<<" "<times<<" "<lenMax<p->lenMax)?max:p->lenMax; p=p->next; } while(p!=head); return max; } int main() { ifstream fin ("beads.in"); char necklace[MAXLEN]; int i,j,max; fin>>necklace; nodeList* list=NULL; int repeat = 0; i=0; while(i
它是一个旧线程，但可能对学习编程的人有用。 这是一个使用蛮力的简单解决方案。 我们的想法是，我们通过数据传递一次来计算颜色。 在第二个循环中，我们对左右两部分的和进行成对比较。 代码应该很容易遵循：
import java.io.*; import java.util.LinkedList; import java.util.List; import java.util.TreeSet; public class beads { public static void main(String[] args) throws IOException { BufferedReader f = new BufferedReader(new FileReader("beads.in")); PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter("beads.out"))); f.readLine();//length String s1 = f.readLine(); List counts = new LinkedList (); char[] colors = (s1.concat(s1)).toCharArray(); char previousColor = ' '; int count = 0; for (char color : colors) { if (previousColor != color && count > 0) { counts.add(count + "-" + previousColor); count = 0; } count++; previousColor = color; } if (counts.isEmpty()) {//special case when there is only one color out.println(count/2); out.close(); System.exit(0); } TreeSet result = new TreeSet (); for (int i = 1; i < counts.size(); i++) { if(counts.get(i).split("-")[1].charAt(0)=='w')continue; int left = getLeft(counts, i); int right = getRight(counts, i); result.add((left+right)); } out.println(result.last()); out.close(); System.exit(0); } private static int getLeft(List counts, int i) { char start = counts.get(i - 1).split("-")[1].charAt(0); boolean doContinue = true; int count = 0; while (doContinue) { String[] s = counts.get(--i).split("-"); char color=s[1].charAt(0); if(start=='w' && color!='w')start=color; boolean incr = (color == 'w' || color==start); if(incr) count += Integer.parseInt(s[0]); else doContinue=false; doContinue = doContinue && i > 0; } return count; } private static int getRight(List counts, int i) { char start = counts.get(i).split("-")[1].charAt(0); boolean doContinue = true; int count = 0; while (doContinue) { String[] s = counts.get(i).split("-"); char color=s[1].charAt(0); if(start=='w' && color!='w')start=color; boolean incr = (color == 'w' || color == start); if(incr) count += Integer.parseInt(s[0]); else doContinue=false; doContinue = doContinue && ++i < counts.size()-1; } return count; } }
这是预告片！ 每次解决方案都如此，如此接近！ 与此同时，白色珠子是黑色绝望的原因。
这是算法（我通过了Usaco分级机）
1）找到第一个彩色珠子。 说它是在n珠项链的位置k
2）重新排列项链：将0-k部分移动到最后，因此它以真彩色开始。 例如{wwbrwbrb {成为{brwbrbww}
3）将项链切成子段（字符串数组），这样每个部分都以一种颜色开始，例如{b rw br bww}
4）如果第一段和最后一段是相同的颜色，请加入它们
例如{b rw bw rw bww}成为{bwwb rw bw rw}（序列被保留）
5）注意!!!! 第二个元素（bw）以白色结尾。 所以white可以加入到随后的rw中。
另请注意，以下序列永远不会以白色开始。
6）对于子序列数组中的每个条目，添加条目k和k + 1的长度。
然后从条目k-1中略过白色空格（如果有的话）并添加到上面（因为这是一个圆圈，那么k-1条目可能是数组中的最后一个）。
如果大于最大值则更改最大值
项链中不到三个子序列有一些棘手的问题，但它只是单调乏味，没有诀窍。