题目大意：有4个长方形，放在一起，不能重叠，然后用一个长方形包围，这个长方形的面积最小为多少，宽度和长度为多少。如果有多组长宽都符合最小的话，那么按照p从大到小输出。

题目中提示只有题中给的6种情况，其他的情况都可以由这6种经过旋转，映像得到。

分析：题目中的6种中4和5其实是一种，旋转和映像得到的长方形应该和不经过旋转是一样的，所以只有5种情况。解题思想就是枚举每一种放置的顺序，然后进行判断，找到最小的面积。对于最后一种情况应该要根据4个长方形的长宽进行分类，具体见代码。

/*
ID: nazgul12
LANG: C
TASK: packrec
*/
#include <stdio.h>
#include <stdlib.h>

typedef struct{ int x, y; } st;

st s[4], xy, sol[100];
int e[4], used[4] = {0};
int mini = 0x7fffffff, l;

void swap( st * t )
{
	int temp;
	temp = t->x; t->x = t->y; t->y = temp;
}

int mmax( int a, int b )
{
	return a > b ? a : b;
}

int sum( int l, int r )
{
	int t = 0, i;
	for ( i = l; i <= r; ++i )
		t += s[e[i]].x;
	return t;
}

int max( int l, int r )
{
	int t = 0, i;
	for ( i = l; i <= r; ++i )
		if ( s[e[i]].y > t )
			t = s[e[i]].y;
	return t;
}

void solve()
{
	int i;
	if ( xy.x > xy.y ) swap( &xy );
	if ( xy.x * xy.y > mini ) return;
	if ( xy.x * xy.y < mini )
	{
		l = 0; mini = xy.x * xy.y;
	}
	if ( xy.x * xy.y == mini )
	{
		for ( i = 0; i < l; ++i )
			if ( xy.x == sol[i].x )
				return;
	}
	sol[l].x = xy.x; sol[l].y = xy.y;
	l++;
}

void test()
{
	xy.x = sum( 0, 3 ); xy.y = max( 0, 3 );
	solve();
	xy.x = mmax( s[e[0]].x, sum( 1, 3 ) );
	xy.y = max( 1, 3 ) + s[e[0]].y;
	solve();
	xy.x = mmax( s[e[0]].x, sum( 1, 2 ) ) + s[e[3]].x;
	xy.y = mmax( s[e[3]].y, mmax( s[e[1]].y, s[e[2]].y ) + s[e[0]].y );
	solve();
	xy.x = mmax( s[e[1]].x, s[e[2]].x ) + s[e[0]].x + s[e[3]].x;
	xy.y = mmax( mmax( s[e[0]].y, s[e[3]].y ), s[e[1]].y + s[e[2]].y );
	solve();
	if ( s[e[1]].y <= s[e[0]].y && s[e[1]].x >= s[e[2]].x &&
		s[e[0]].x <= s[e[3]].x && s[e[3]].y <= s[e[2]].y )
		{
			xy.x = mmax( s[e[0]].x+s[e[1]].x , s[e[2]].x+s[e[3]].x );
			xy.y = mmax( s[e[0]].y+s[e[3]].y , s[e[1]].y+s[e[2]].y );
			solve();
		}
	if ( s[e[0]].x <= s[e[1]].x && s[e[2]].x <= s[e[3]].x )
	{
		xy.x = s[e[1]].x + s[e[3]].x;
		xy.y = mmax( s[e[0]].y+s[e[1]].y, s[e[2]].y+s[e[3]].y );
		solve();
	}
}

void dfs( int k )
{
	int i;
	if ( k == 4 ) test();
	else
	{
		for ( i = 0; i < 4; ++i )
			if ( used[i] == 0 )
			{
				e[k] = i; used[i] = 1;
				dfs( k + 1 );
				swap( s+i );
				dfs( k + 1 );
				swap( s+i );
				used[i] = 0;
			}
	}
}

int cmp( const void *a, const void *b )
{
	return ( ( st * )a )->x - ( ( st * )b )->x;
}

int main()
{
	int i;
	freopen( "packrec.in", "r", stdin );
	freopen( "packrec.out", "w", stdout );
	for ( i = 0; i < 4; ++i )
		scanf( "%d%d", &s[i].x, &s[i].y );
	dfs( 0 );
	printf( "%d\n", mini );
	qsort( sol, l, sizeof( sol[0] ), cmp );
	for ( i = 0; i < l; ++i )
		printf( "%d %d\n", sol[i].x, sol[i].y );
	return 0;
}

USACO TRAINING Section 1.1

Broken Necklace

You have a necklace of N red, white, or blue beads (3<=N<=350) some of which are red, others blue, and others white, arranged at random. Here are two examples for n=29:
1 2 1 2
r b b r b r r b
r b b b
r r b r
r r w r
b r w w
b b r r
b b b b
b b r b
r r b r
b r r r
b r r r
r r r b
r b r r r w
Figure A Figure B
r red bead
b blue bead
w white bead

The beads considered first and second in the text that follows have been marked in the picture.

The configuration in Figure A may be represented as a string of b's and r's, where b represents a blue bead and r represents a red one, as follows: brbrrrbbbrrrrrbrrbbrbbbbrrrrb .

Suppose you are to break the necklace at some point, lay it out straight, and then collect beads of the same color from one end until you reach a bead of a different color, and do the same for the other end (which might not be of the same color as the beads collected before this).

Determine the point where the necklace should be broken so that the most number of beads can be collected.
Example

For example, for the necklace in Figure A, 8 beads can be collected, with the breaking point either between bead 9 and bead 10 or else between bead 24 and bead 25.

In some necklaces, white beads had been included as shown in Figure B above. When collecting beads, a white bead that is encountered may be treated as either red or blue and then painted with the desired color. The string that represents this configuration will include the three symbols r, b and w.

Write a program to determine the largest number of beads that can be collected from a supplied necklace.
PROGRAM NAME: beads
INPUT FORMATLine 1: N, the number of beads
Line 2: a string of N characters, each of which is r, b, or w

SAMPLE INPUT (file beads.in)
29
wwwbbrwrbrbrrbrbrwrwwrbwrwrrb
OUTPUT FORMAT
A single line containing the maximum of number of beads that can be collected from the supplied necklace.
SAMPLE OUTPUT (file beads.out)
11
OUTPUT EXPLANATION
Consider two copies of the beads (kind of like being able to runaround the ends). The string of 11 is marked.
wwwbbrwrbrbrrbrbrwrwwrbwrwrrb wwwbbrwrbrbrrbrbrwrwwrbwrwrrb
****** *****

题目大意：你有一个项链，项链上的珠子颜色有红白蓝三种颜色，将项链从一个地方断开，然后展开成直线，然后从一头开始收集珠子，直到碰到其他颜色的，然后在另一头也一样收集。当从某个地方断开时，可以收集到最多的珠子，问最多收集到多少个。
注意：白色的珠子可以算成红色的或者是蓝色的。
样列：
29
wwwbbrwrbrbrrbrbrwrwwrbwrwrrb
从倒数6和7中间断开，可以收集到最多的个数11

1。最简单的方法就是从每个地方断开，然后统计最多的，复杂度O(n^2)。
2。贪心：输入的s是一个环，所以前后可以相连，为了方便，再复制一份在原来的后面成ss，这样收集到的珠子就应该是相邻的。为了收集到最多，断开点绝对不会是同一种颜色的珠子中间，只能是在边界上断开。因此直观的思想就是先计算在一起的相同颜色的有多少个，然后取相邻2种不同颜色最多的个数。比如题目中的样列brbrrrbbbrrrrrbrrbbrbbbbrrrrb，先复制成ss，brbrrrbbbrrrrrbrrbbrbbbbrrrrbbrbrrrbbbrrrrrbrrbbrbbbbrrrrb
统计在一起的相同颜色的珠子个数：1b1r1b3r3b5r1b2r2b1r4b4r2b1r1b3r3r5r1b2r2b1r4b4r1b，然后取相邻2种不同颜色最多的个数。由于白色的可以表示成红色或蓝色，所以白色的要特殊处理。但是像bbwwwbb中间的www应该直接算作b，这样才能取到最多。
下面代码中pre数组用于记录，pre[i]表示与s[i]颜色不同的珠子最近的位置，所以i-pre[i]就是这种颜色在一起的个数，再加上pre[i]到pre[pre[i]]的个数，就是能收集到的个数。其他解释见代码。

#include <stdio.h>
#include <string.h>

char s[701] = {0}, cur, flag; //cur用于标记当前珠子的颜色
int n, pre[701];

int main()
{
	int i, nn, t, k;
	freopen( "beads.in", "r", stdin );
	freopen( "beads.out", "w", stdout );
	memset( pre, -1, sizeof( pre ) );
	scanf( "%d%s", &n, s );
	//将s复制成ss
	for ( flag = cur = i = 0; i < n; ++i )
	{
		s[n+i] = s[i];
		//找到最开始的颜色		
		if ( !cur && s[i] != 'w' ) cur = s[i];
		//flag用于标示s是否只有一种颜色		
		if ( s[i] != s[0] ) flag = 1;
	}
	//如果只有一种颜色
	if ( !cur || !flag )
	{
		printf( "%d\n", n ); return 0;
	}
	//t用于记录当前颜色出现的开始位置
	i = 1; t = 0; k = -1; nn = ( n<<1 )-1;
	//k用于记录w是否可以表示成2种颜色，如果w是在同一种颜色的中间，k为-1,否则k为可以表示成2种颜色的最开始出现的位置
	//比如rrwwwb,则要记录最开始w出现的位置
	while ( i < nn )
	{
		if ( s[i]=='w' || s[i] == cur )
		{
			if ( k == -1 && s[i] == 'w' )
				k = i;
			else k = -1;
			i++;
		}
		else
		{
			pre[i-1] = t-1; cur = s[i];
			if ( k != -1 )
			{
				i = k; pre[i-1] = t-1;
			}
			t = ++i-1;
		}
	}
	t = 0;
	for ( i = 0; i < nn; ++i )
		if ( pre[i] != -1 )
		{
			k = i - pre[pre[i]];
			if ( t < k ) t = k;
		}
	printf( "%d\n", t );
	return 0;
}