这是这一次做USACO目前唯一一个没做完的题目！第六种情况实在是不知道怎么写，我觉得最好还是不写最好，所以就没去写了。我也尝试了一下自己试着写写，结果写了最后一种情况竟然还不如不写的分数高！但是自己实在是不知道为什么，以前的代码这三行（最后一种情况）也是抄的，不是理解的，所以现在也就忘了……
我的思路就是暴搜，用srch0将所用的矩形换位置，srch1将所有的矩阵的长宽交换，然后用count进行判断，代码十分易读（以前别人写的，不过因为确实有特色，所以已经变成了自己的东西了。）
总结一下错误：
注意：本程序还没AC，但是要他AC只需要最后的两个if，因为我不理解缘由，所以没写第六种情况（代码中注释好了！）
LANG: C
ID: yylogoo2
PROG: packrec
/
#include <math.h>
#include <stdio.h>
#include <string.h>
struct box{
int x, y;
}box[4];
int place[4];
int ans = 2501;
int take[2501];
void check(int x, int y)
{
if(x y < ans){
ans = x y;
memset(take, 0, sizeof(take));
}
/
Mistack 3:
没经过任何判断就直接把x, y作为答案了，那么就错了！！
即刚刚忘记敲入if了。
/
if(x y == ans){
take[x] = 1;
take[y] = 1;
}
}
int max(int a, int b)
{
return a > b ? a : b;
}
void count(int x1, int y1, int x2, int y2,
int x3, int y3, int x4, int y4)
{
int x, y;
x = x1 + x2 + x3 + x4;
y = max(max(y1, y2), max(y3, y4));
check(x, y);
x = max(x1, x2 + x3 + x4);
y = y1 + max(y2, max(y3, y4));
check(x, y);
x = max(x1, x2 + x3) + x4;
y = max(y4, y1 + max(y2, y3));
check(x, y);
x = x1 + max(x2, x3) + x4;
/
Mistack 4:
下面把y写成了x
/
y = max(y2 + y3, max(y1, y4));
check(x, y);
/ 最后一种情况 /
}
void output(void)
{
int i, limit;
printf("%d\n", ans);
limit = sqrt(ans);
for(i = 1; i <= limit; i++){
if(take[i]){
printf("%d %d\n", i, ans / i);
}
}
}
void change(struct box a)
{
a->x ^= a->y;
a->y ^= a->x;
a->x ^= a->y;
}
void srch1(int now)
{
if(now == 4){
count( box[place[0]].x, box[place[0]].y,
box[place[1]].x, box[place[1]].y,
box[place[2]].x, box[place[2]].y,
box[place[3]].x, box[place[3]].y);
return;
}
srch1(now + 1);
change(&box[place[now]]);
srch1(now + 1);
change(&box[place[now]]);
}
int used[4];
void srch0(int now)
{
int i;
if(now == 4){
/
Mistack 2:
是调用srch1(0)而不是srch(now + 1)
/
srch1(0);
/
Mistack 1:
把函数返回掉了…那样会死循环的..
/
return;
}
for(i = 0; i < 4; i++){
if(!used[i]){
used[i] = 1;
place[now] = i;
srch0(now + 1);
used[i] = 0;
}
}
}
int main(void)
{
int i;
freopen("packrec.in", "r", stdin);
freopen("packrec.out", "w", stdout);
for(i = 0; i < 4; i++){
scanf("%d%d", &box[i].x, &box[i].y);
}
srch0(0);
output();
return 0;
}