USACO Section 1.4 Packing Rectangles （POJ 1169）搜索

2023-11-08 09:39
文章标签 搜索 1.4 poj usaco section packing 1169 rectangles

本文主要是介绍USACO Section 1.4 Packing Rectangles （POJ 1169）搜索，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

这是一个很蛋疼的搜索题，虽然题中只给了5种矩形组合方式，但是搜索时的长和宽并不是唯一的，所以就产生了很多种组合方式.需要注意的是第4种和第3种图形实际上能规划成一种。 而产生这些组合最好用的应该就是DFS了，而我当时不想动脑子，使用的就是纯枚举，巨大的代码量，最终好歹也能过了。

/*
ID: sdj22251
PROG: packrec
LANG: C++
*/
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define MAX 2000000000
#define M 1007
#define LOCAL
using namespace std;
struct wwj
{int x, y;
}a[4], ans[21050];
bool v[5];
wwj f1(wwj a, wwj b, wwj c, wwj d)
{wwj rec;rec.x = a.x + b.x + c.x + d.x;rec.y = max(max(a.y, b.y), max(c.y, d.y));return rec;
}
wwj f2(wwj a, wwj b, wwj c, wwj d)
{wwj rec;rec.x = max(a.x, b.x + c.x + d.x);rec.y = a.y + max(d.y, max(b.y, c.y));return rec;
}
wwj f3(wwj a, wwj b, wwj c, wwj d)
{wwj rec;rec.x = max(a.x+b.x, c.x)+d.x;rec.y = max(max(a.y, b.y)+c.y, d.y);return rec;
}
wwj f4(wwj a, wwj b, wwj c, wwj d)
{wwj rec;rec.x = a.x + max(b.x, c.x) + d.x;rec.y = max(max(a.y, b.y + c.y), d.y);return rec;
}
wwj f6(wwj a, wwj b, wwj c, wwj d)
{wwj rec;rec.x = a.x+b.x;rec.y = max(a.y+c.y, b.y+d.y);if (a.y < b.y)rec.x = max(rec.x, c.x+b.x);if (a.y+c.y > b.y)rec.x = max(rec.x, c.x+d.x);if (b.y < a.y)rec.x = max(rec.x, a.x+d.x);rec.x = max(rec.x, c.x);rec.x = max(rec.x, d.x);return rec;
}
bool cmp(wwj a, wwj b)
{if(a.x * a.y == b.x * b.y)return a.x < b.x;else return a.x * a.y < b.x * b.y;
}
int main()
{
#ifdef LOCALfreopen("packrec.in","r",stdin);freopen("packrec.out","w",stdout);
#endifint i, j, k, q;int count = 0;for(i = 0; i < 4; i++)scanf("%d%d", &a[i].x, &a[i].y);for(i = 0; i < 4; i++){v[i] = true;for(j = 0; j < 4; j++){if(v[j] == true)continue;v[j] = true;for(k = 0; k < 4; k++){if(v[k] == true)continue;v[k] = true;for(q = 0; q < 4; q++){if(v[q] == true)continue;wwj fk1, fk2, fk3, fk4;fk1.x = a[i].y;fk1.y = a[i].x;fk2.x = a[j].y;fk2.y = a[j].x;fk3.x = a[k].y;fk3.y = a[k].x;fk4.x = a[q].y;fk4.y = a[q].x;ans[count++] = f1(a[i], a[j], a[k], a[q]);ans[count++] = f2(a[i], a[j], a[k], a[q]);ans[count++] = f3(a[i], a[j], a[k], a[q]);ans[count++] = f4(a[i], a[j], a[k], a[q]);ans[count++] = f6(a[i], a[j], a[k], a[q]);ans[count++] = f1(fk1, a[j], a[k], a[q]);ans[count++] = f2(fk1, a[j], a[k], a[q]);ans[count++] = f3(fk1, a[j], a[k], a[q]);ans[count++] = f4(fk1, a[j], a[k], a[q]);ans[count++] = f6(fk1, a[j], a[k], a[q]);ans[count++] = f1(fk1, a[j], fk3, a[q]);ans[count++] = f2(fk1, a[j], fk3, a[q]);ans[count++] = f3(fk1, a[j], fk3, a[q]);ans[count++] = f4(fk1, a[j], fk3, a[q]);ans[count++] = f6(fk1, a[j], fk3, a[q]);ans[count++] = f1(fk1, a[j], a[k], fk4);ans[count++] = f2(fk1, a[j], a[k], fk4);ans[count++] = f3(fk1, a[j], a[k], fk4);ans[count++] = f4(fk1, a[j], a[k], fk4);ans[count++] = f6(fk1, a[j], a[k], fk4);ans[count++] = f1(fk1, fk2, a[k], a[q]);ans[count++] = f2(fk1, fk2, a[k], a[q]);ans[count++] = f3(fk1, fk2, a[k], a[q]);ans[count++] = f4(fk1, fk2, a[k], a[q]);ans[count++] = f6(fk1, fk2, a[k], a[q]);ans[count++] = f1(fk1, fk2, a[k], fk4);ans[count++] = f2(fk1, fk2, a[k], fk4);ans[count++] = f3(fk1, fk2, a[k], fk4);ans[count++] = f4(fk1, fk2, a[k], fk4);ans[count++] = f6(fk1, fk2, a[k], fk4);ans[count++] = f1(fk1, fk2, fk3, a[q]);ans[count++] = f2(fk1, fk2, fk3, a[q]);ans[count++] = f3(fk1, fk2, fk3, a[q]);ans[count++] = f4(fk1, fk2, fk3, a[q]);ans[count++] = f6(fk1, fk2, fk3, a[q]);ans[count++] = f1(fk1, fk2, fk3, fk4);ans[count++] = f2(fk1, fk2, fk3, fk4);ans[count++] = f3(fk1, fk2, fk3, fk4);ans[count++] = f4(fk1, fk2, fk3, fk4);ans[count++] = f6(fk1, fk2, fk3, fk4);ans[count++] = f1(a[i], fk2, a[k], a[q]);ans[count++] = f2(a[i], fk2, a[k], a[q]);ans[count++] = f3(a[i], fk2, a[k], a[q]);ans[count++] = f4(a[i], fk2, a[k], a[q]);ans[count++] = f6(a[i], fk2, a[k], a[q]);ans[count++] = f1(a[i], fk2, a[k], fk4);ans[count++] = f2(a[i], fk2, a[k], fk4);ans[count++] = f3(a[i], fk2, a[k], fk4);ans[count++] = f4(a[i], fk2, a[k], fk4);ans[count++] = f6(a[i], fk2, a[k], fk4);ans[count++] = f1(a[i], fk2, fk3, a[q]);ans[count++] = f2(a[i], fk2, fk3, a[q]);ans[count++] = f3(a[i], fk2, fk3, a[q]);ans[count++] = f4(a[i], fk2, fk3, a[q]);ans[count++] = f6(a[i], fk2, fk3, a[q]);ans[count++] = f1(a[i], fk2, fk3, fk4);ans[count++] = f2(a[i], fk2, fk3, fk4);ans[count++] = f3(a[i], fk2, fk3, fk4);ans[count++] = f4(a[i], fk2, fk3, fk4);ans[count++] = f6(a[i], fk2, fk3, fk4);ans[count++] = f1(a[i], a[j], fk3, a[q]);ans[count++] = f2(a[i], a[j], fk3, a[q]);ans[count++] = f3(a[i], a[j], fk3, a[q]);ans[count++] = f4(a[i], a[j], fk3, a[q]);ans[count++] = f6(a[i], a[j], fk3, a[q]);ans[count++] = f1(a[i], a[j], fk3, fk4);ans[count++] = f2(a[i], a[j], fk3, fk4);ans[count++] = f3(a[i], a[j], fk3, fk4);ans[count++] = f4(a[i], a[j], fk3, fk4);ans[count++] = f6(a[i], a[j], fk3, fk4);ans[count++] = f1(a[i], a[j], a[k], fk4);ans[count++] = f2(a[i], a[j], a[k], fk4);ans[count++] = f3(a[i], a[j], a[k], fk4);ans[count++] = f4(a[i], a[j], a[k], fk4);ans[count++] = f6(a[i], a[j], a[k], fk4);}v[k] = false;}v[j] = false;}v[i] = false;}sort(ans, ans + count, cmp);printf("%d\n", ans[0].x * ans[0].y);int t = ans[0].x * ans[0].y;for(i = 0; i < count; i++){if(ans[i].x * ans[i].y == t){ans[i].x = min(ans[i].x, ans[i].y);ans[i].y = t / ans[i].x;}}sort(ans, ans + count, cmp);for(i = 0; i < count; i++){if(ans[i].x * ans[i].y == ans[0].x * ans[0].y){if(i >= 1 && ans[i].x == ans[i - 1].x)continue;printf("%d %d\n", ans[i].x, ans[i].y);}}return 0;
}
附官方题解一份，代码风格让我觉得很飘渺，怎么也看的不是很懂

This program is straightforward, but a bit long due to the geometry involved.

There are 24 permutations of the 4 rectangles, and for each permutation, 16 different ways to orient them. 

We generate all such orientations of permutations, and put the blocks together in each of the 6 different ways, recording the smallest rectangles we find.


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>typedef struct Rect Rect;
struct Rect {int wid;int ht;
};Rect
rotate(Rect r)
{Rect nr;nr.wid = r.ht;nr.ht = r.wid;return nr;
}int
max(int a, int b)
{return a > b ? a : b;
}int
min(int a, int b)
{return a < b ? a : b;
}int tot;
int bestarea;
int bestht[101];void
record(Rect r)
{int i;if(r.wid*r.ht < tot)*(long*)0=0;if(r.wid*r.ht < bestarea || bestarea == 0) {bestarea = r.wid*r.ht;for(i=0; i<=100; i++)bestht[i] = 0;}if(r.wid*r.ht == bestarea)bestht[min(r.wid, r.ht)] = 1;
}void
check(Rect *r)
{Rect big;int i;/* schema 1: all lined up next to each other */big.wid = 0;big.ht = 0;for(i=0; i<4; i++) {big.wid += r[i].wid;big.ht = max(big.ht, r[i].ht);}record(big);/* schema 2: first three lined up, fourth on bottom */big.wid = 0;big.ht = 0;for(i=0; i<3; i++) {big.wid += r[i].wid;big.ht = max(big.ht, r[i].ht);}big.ht += r[3].ht;big.wid = max(big.wid, r[3].wid);record(big);/* schema 3: first two lined up, third under them, fourth to side */big.wid = r[0].wid + r[1].wid;big.ht = max(r[0].ht, r[1].ht);big.ht += r[2].ht;big.wid = max(big.wid, r[2].wid);big.wid += r[3].wid;big.ht = max(big.ht, r[3].ht);record(big);/* schema 4, 5: first two rectangles lined up, next two stacked */big.wid = r[0].wid + r[1].wid;big.ht = max(r[0].ht, r[1].ht);big.wid += max(r[2].wid, r[3].wid);big.ht = max(big.ht, r[2].ht+r[3].ht);record(big);/** schema 6: first two pressed next to each other, next two on top, like: * 2 3* 0 1*/big.ht = max(r[0].ht+r[2].ht, r[1].ht+r[3].ht);big.wid = r[0].wid + r[1].wid;/* do 2 and 1 touch? */if(r[0].ht < r[1].ht)big.wid = max(big.wid, r[2].wid+r[1].wid);/* do 2 and 3 touch? */if(r[0].ht+r[2].ht > r[1].ht)big.wid = max(big.wid, r[2].wid+r[3].wid);/* do 0 and 3 touch? */if(r[1].ht < r[0].ht)big.wid = max(big.wid, r[0].wid+r[3].wid);/* maybe 2 or 3 sits by itself */big.wid = max(big.wid, r[2].wid);big.wid = max(big.wid, r[3].wid);record(big);    
}void
checkrotate(Rect *r, int n)
{if(n == 4) {check(r);return;}checkrotate(r, n+1);r[n] = rotate(r[n]);checkrotate(r, n+1);r[n] = rotate(r[n]);
}void
checkpermute(Rect *r, int n)
{Rect t;int i;if(n == 4)checkrotate(r, 0);for(i=n; i<4; i++) {t = r[n], r[n] = r[i], r[i] = t;    /* swap r[i], r[n] */checkpermute(r, n+1);t = r[n], r[n] = r[i], r[i] = t;    /* swap r[i], r[n] */}
}void
main(void)
{FILE *fin, *fout;Rect r[4];int i;fin = fopen("packrec.in", "r");fout = fopen("packrec.out", "w");assert(fin != NULL && fout != NULL);for(i=0; i<4; i++)fscanf(fin, "%d %d", &r[i].wid, &r[i].ht);tot=(r[0].wid*r[0].ht+r[1].wid*r[1].ht+r[2].wid*r[2].ht+r[3].wid*r[3].ht);checkpermute(r, 0);fprintf(fout, "%d\n", bestarea);for(i=0; i<=100; i++)if(bestht[i])fprintf(fout, "%d %d\n", i, bestarea/i);exit(0);
}



这篇关于USACO Section 1.4 Packing Rectangles （POJ 1169）搜索的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/369048。

相关文章

认识、理解、分类——acm之搜索

认识、理解、分类——acm之搜索

普通搜索方法有两种：1、广度优先搜索；2、深度优先搜索； 更多搜索方法： 3、双向广度优先搜索； 4、启发式搜索（包括A*算法等）； 搜索通常会用到的知识点：状态压缩（位压缩，利用hash思想压缩）。
阅读更多...
hdu1240、hdu1253（三维搜索题）

hdu1240、hdu1253（三维搜索题）

1、从后往前输入，（x，y，z）; 2、从下往上输入，（y , z, x）; 3、从左往右输入，（z，x，y）； hdu1240代码如下： #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#inc
阅读更多...
usaco 1.3 Prime Cryptarithm(简单哈希表暴搜剪枝)

usaco 1.3 Prime Cryptarithm(简单哈希表暴搜剪枝)

思路： 1. 用一个 hash[ ] 数组存放输入的数字，令 hash[ tmp ]=1 。 2. 一个自定义函数 check( ) ，检查各位是否为输入的数字。 3. 暴搜。第一行数从 100到999，第二行数从 10到99。 4. 剪枝。 代码： /*ID: who jayLANG: C++TASK: crypt1*/#include<stdio.h>bool h
阅读更多...
usaco 1.3 Calf Flac（暴搜）

usaco 1.3 Calf Flac（暴搜）

思路是暴搜。 需要注意的地方是输入的方法，以及输出时的换行。 代码： /*ID: who jayLANG: C++TASK: calfflac*/#include<stdio.h>#include<string.h>#include<math.h>int main(){freopen("calfflac.in","r",stdin);freopen("calfflac.ou
阅读更多...
usaco 1.3 Barn Repair（贪心）

usaco 1.3 Barn Repair（贪心）

思路：用上M块木板时有 M-1 个间隙。目标是让总间隙最大。将相邻两个有牛的牛棚之间间隔的牛棚数排序，选取最大的M-1个作为间隙，其余地方用木板盖住。 做法： 1.若，板（M） 的数目大于或等于 牛棚中有牛的数目（C），则 目测 给每个牛牛发一个板就为最小的需求~ 2.否则，先对 牛牛们的门牌号排序，然后 用一个数组 blank[ ] 记录两门牌号之间的距离，然后 用数组 an
阅读更多...
usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心： 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数，若返回值为正，qsort 函数判定a>b ；为负，a<b；为0，a==b； int milkcmp(const void *va,c
阅读更多...
usaco 1.2 Palindromic Squares（进制转化）

usaco 1.2 Palindromic Squares（进制转化）

考察进制转化 注意一些细节就可以了 直接上代码： /*ID: who jayLANG: C++TASK: palsquare*/#include<stdio.h>int x[20],xlen,y[20],ylen,B;void change(int n){int m;m=n;xlen=0;while(m){x[++xlen]=m%B;m/=B;}m=n*n;ylen=0;whi
阅读更多...
usaco 1.2 Name That Number（数字字母转化）

usaco 1.2 Name That Number（数字字母转化）

巧妙的利用code[b[0]-'A'] 将字符ABC...Z转换为数字 需要注意的是重新开一个数组 c [ ] 存储字符串 应人为的在末尾附上 ‘ \ 0 ’ 详见代码： /*ID: who jayLANG: C++TASK: namenum*/#include<stdio.h>#include<string.h>int main(){FILE *fin = fopen (
阅读更多...
usaco 1.2 Milking Cows（类hash表）

usaco 1.2 Milking Cows（类hash表）

第一种思路被卡了时间 到第二种思路的时候就觉得第一种思路太坑爹了 代码又长又臭还超时！！ 第一种思路：我不知道为什么最后一组数据会被卡 超时超了0.2s左右 大概想法是 快排加一个遍历 先将开始时间按升序排好 然后开始遍历比较 1 若 下一个开始beg[i] 小于 tem_end 则说明本组数据与上组数据是在连续的一个区间 取max( ed[i],tem_end ) 2 反之 这个
阅读更多...
usaco 1.2 Transformations（模拟）

usaco 1.2 Transformations（模拟）

我的做法就是一个一个情况枚举出来 注意计算公式： （ 变换后的矩阵记为C） 顺时针旋转90°：C[i] [j]=A[n-j-1] [i] （旋转180°和270° 可以多转几个九十度来推） 对称：C[i] [n-j-1]=A[i] [j] 代码有点长 。。。 /*ID: who jayLANG: C++TASK: transform*/#include<
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2