USACO Broken Necklace

寫得很爛，根本不知道可以怎麼做，囧。
只好硬幹。寫到快起肖，悲劇。

先找每組珠子的數目數，之後存起來，
接著找最大的珠子數，
再檢查該珠子的兩側（因為環狀），
是否有算錯，
例如bwrwb可能是1 3 1或2 1 2。
沒錯的話就可以輸出。

/*
ID: mythnc2
LANG: C
TASK: Beads
Broken Necklace
2011/10/27 11:41:05   
*/
#include <stdio.h>
#include <string.h>

#define MAXARY 360

typedef struct record{
    int count;
    char *head, *tail;
} Record;

int firstlen(char *);
void movefirst(char *, int);
char *len(char *, Record *, int *);
int backward(char *);
int maxvalue(Record *, int);
int pairs(Record *, Record);
int reverse(char *, char *);

int main(void)
{
    FILE *fin, *fout;
    char bead[MAXARY];
    char *move;
    Record rec[MAXARY];
    int n, i, step;

    fin = fopen("beads.in", "r");
    fout = fopen("beads.out", "w");
    
    fscanf(fin, "%d", &n);
    fscanf(fin, "%s", bead);

    if ((i = firstlen(bead)) == n) {  /* one color */
        fprintf(fout, "%d\n", i);
        return 0;
    }
    else
        movefirst(bead, i);

    for (move = bead, i = 0; *move; i++) {
        move = len(move, &rec[i], &step);
        if (step)
            i++;
    }

    if (i < 3)
        fprintf(fout, "%d\n", rec[0].count + rec[1].count);
    else
        fprintf(fout, "%d\n", maxvalue(rec, i));

    return 0;
}

/* firstlen: count the first length
 * also use this function to count w length */
int firstlen(char *bead)
{
    int i;

    i = 0;
    /* if first char is w, skip over it */
    while (bead[i] == 'w')
        i++;
    if (bead[i] == '\0')   /* all beads is w color */
        return i;

    if (bead[i] == 'b')
        while (bead[i] == 'b' || bead[i] == 'w')
            i++;
    else
        while (bead[i] == 'r' || bead[i] == 'w')
            i++;
    return i;
}

/* movefirst: rearrange string bead,
 * move the first len to last */
void movefirst(char *bead, int n)
{
    int i;
    char tmp[n];

    strncpy(tmp, bead, n);
    for (i = 0; bead[i + n] != '\0'; i++)
        bead[i] = bead[i + n];
    bead[i] = '\0';
    strncat(bead, tmp, n);
}

/* len: count the len of each color bead
 * and return the position after count */
char *len(char *move, Record *rec, int *step)
{
    int wcount;
    char *w;

    wcount = rec->count = *step = 0;
    rec->head = move;
    if (*move == 'b')
        while (*move == 'b' || *move == 'w') {
            if (*move == 'w' && wcount == 0) {
                wcount = firstlen(move);
                w = move;
            }
            rec->count++;
            move++;
        }
    else  /* color r */
        while (*move == 'r' || *move == 'w') {
            if (*move == 'w' && wcount == 0) {
                wcount = firstlen(move);
                w = move;
            }
            rec->count++;
            move++;
        }

    if (wcount > rec->count) {
        *step = 1;
        rec->count -= backward(move); /* corrected count */
        move = w + wcount;            /* corrected position */
        rec->tail = w;
        (++rec)->count = wcount;      /* the next count value */
        rec->head = w;
    }
    rec->tail = move;
    return move;
}

/* backward: backward pointer to find previous color,
 * which is not w color return the backward steps */
int backward(char *back)
{
    int count;

    count = 0;
    while (*--back == 'w')
        count++;

    return count;
}

/* maxvalue: find the max element
 * if max is not only one, judge them sequentially
 * return the biggest count of this element 
 * and its adjacence */
int maxvalue(Record *rec, int n)
{
    int i, max, count, tmp;
    int index[MAXARY];

    for (max = i = 0; i < n; i++)
        if (rec[max].count < rec[i].count)
            max = i;
    /* find the number of max */
    for (count = i = 0; i < n; i++)
        if (rec[max].count == rec[i].count)
            index[count++] = i;

    for (max = i = 0; i < count; i++) {
        if (index[i] == 1)
            tmp = pairs(&rec[n - 1], rec[2]) + rec[0].count;
        else if (index[i] == 0)
            tmp = pairs(&rec[n - 2], rec[1]) + rec[0].count;
        else if (index[i] == n - 1)
            tmp = pairs(&rec[n - 3], rec[0]) + rec[n - 1].count;
        else
            tmp = pairs(&rec[index[i] - 2], rec[index[i] + 1])
                   + rec[index[i]].count;
        if (tmp > max)
            max = tmp;
    }
    return max;
}

/* pairs: recalculate pre and next len
 * return the largest */
int pairs(Record *pre, Record next)
{
    int pv, nv;

    nv = firstlen(next.head);
    pv = reverse(pre->head, pre[1].tail);

    return nv > pv ? nv : pv;
}

/* reverse: reverse the beads before max,
 * recalulate it's len and return it */
int reverse(char *head, char *tail)
{
    char seq[MAXARY];
    char *move;
    int i;

    for (i = 0, move = tail - 1; move > head - 1; move--)
        seq[i++] = *move;
    seq[i] = '\0';

    return firstlen(seq);
}