题意分析:
给出4个长方形的高和长,以及给出6种基本布局,求合成无重叠的最小面积时的长和宽。
解题思路:
这一题比较容易成为被卡住的第一题。
【首先】使用贪心的念头不要有,必须老老实实地将所有情况列出,那到底有多少情况呢?
1.六种基本布局中,第四种与第五种实则为一种,布局为5种。
2.在每种布局中,由于长方形摆放的位置不同,有4的阶乘种。
3.不同布局,不同摆放位置的每个长方形都有横竖两种摆法,有2的4次方种。
综上:共有 5 × 4! × 2^4 = 1920种。
【其次】要回忆一下回溯法。
在S1×S2×S3×…×Sn中,求解向量X=(x1,x2,x3…xn)。
算法描述:
子集树和排列树为常见的两种解空间树。
子集树:遍历子集树需要O(n^2)的时间
排列树:遍历排列树需要O(n!)的时间
回溯法backtracking经常会和术语深度优先遍历DFS(Depth First Search)混用,它们有什么差别呢?
非要深究的话,深度优先搜索是一种遍历真实存在的图或树的方法。而回溯法则是遍历整个问题空间寻找一个解决方案。回溯法是一个更通用的算法,问题本身并不一定与树相关。
【最后】在于每种布局的情况讨论,(这里的h与w,h不一定大于w,反之亦然)
第六种情况的width则要进一步分情况讨论:
代码实现:
https://github.com/leonlu/USACOJavaSolution/blob/master/USACOSection1/src/packrec.java
给出4个长方形的高和长,以及给出6种基本布局,求合成无重叠的最小面积时的长和宽。
解题思路:
这一题比较容易成为被卡住的第一题。
【首先】使用贪心的念头不要有,必须老老实实地将所有情况列出,那到底有多少情况呢?
1.六种基本布局中,第四种与第五种实则为一种,布局为5种。
2.在每种布局中,由于长方形摆放的位置不同,有4的阶乘种。
3.不同布局,不同摆放位置的每个长方形都有横竖两种摆法,有2的4次方种。
综上:共有 5 × 4! × 2^4 = 1920种。
【其次】要回忆一下回溯法。
在S1×S2×S3×…×Sn中,求解向量X=(x1,x2,x3…xn)。
算法描述:
1.令解向量X={} 2.flag=false; 3.advance(1) 4.if(flag) 输出解X 5.else 输出无解 advance(int t): 对每一个x属于St循环执行: X[t] = x; //将xt加入X if(X是最终解)flag=true; return; else if(X是部分解)advance(t+1); //搜索下一层 else(X不是最终解也不是部分解)continue;
子集树和排列树为常见的两种解空间树。
子集树:遍历子集树需要O(n^2)的时间
void backtrack (int t){ if (t>n) output(X); // X是最终解 else{ X[t]=true; if (legal(t)) backtrack (t+1); // X是部分解 X[t]= false; if (legal(t)) backtrack (t+1); // X是部分解 } }
排列树:遍历排列树需要O(n!)的时间
void backtrack (int t) { if (t>n) output(X); // X是最终解 else for (int i=t;i<=n;i++) { swap(x[t], x[i]); if (legal(t)) backtrack(t+1); // X是部分解 swap(x[t], x[i]); } }
回溯法backtracking经常会和术语深度优先遍历DFS(Depth First Search)混用,它们有什么差别呢?
非要深究的话,深度优先搜索是一种遍历真实存在的图或树的方法。而回溯法则是遍历整个问题空间寻找一个解决方案。回溯法是一个更通用的算法,问题本身并不一定与树相关。
【最后】在于每种布局的情况讨论,(这里的h与w,h不一定大于w,反之亦然)
//1: int width = w1 + w2 + w3 + w4; int height = max(max(h1, h2),max(h3, h4)); //2: height = w1 + max(max(h2, h3),h4); width = max(h1, w2 + w3 + w4); a[1] = new Rectangle(width, height); //3: height = max(h1, w2 + max(h3, h4)); width = w1 + max(h2, w3 + w4); a[2] = new Rectangle(width, height); //4,5: width = max(w2,w4) + w1 + w3; height= max(max(h1, h3),h2 + h4); //6: height = max(h1+h3, h2+h4);
第六种情况的width则要进一步分情况讨论:
if(h3 >= h2 + h4) width = max(w1, max(w3+w2,w3+w4)); else if (h3 > h4 && h3 < h2+h4) width = max(max(w1+w2, w2+w3),w3+w4); else if( h3 < h4 && h4 < h1+h3) width = max(max(w1+w2, w1+w4), w3+w4); else if (h4 >=h1+h3) width = max(max(w1+w4, w3+w4), w2); else // h4 == h3 width = max(w1+w2, w3+w4);
代码实现:
https://github.com/leonlu/USACOJavaSolution/blob/master/USACOSection1/src/packrec.java
发表评论
-
USACO Section 1.5.4 [Checker Challenge] Java题解
2011-07-15 23:16 1664题意分析: 该题是需要深度优化的八皇后问题,首先看一下,经典八 ... -
USACO Section 1.5.3 [Superprime Rib] Java题解
2011-07-15 22:24 1509题意分析: 7331是素数,733是素数,73是素数,7也是素 ... -
USACO Section 1.5.2 [Prime Palindromes] Java题解
2011-07-15 22:12 1414题意分析: 找出a和b间既对称既是素数的数。 解题思路: 用 ... -
USACO Section 1.5.1 [Number Triangles] Java题解
2011-07-15 21:21 759题意分析: 数字三角形,找到从顶到底的最大和的通路。 解题思 ... -
USACO Section 1.4.4 [Mother's Milk] Java题解
2011-07-15 18:57 1271题意分析: 有容量为A,B,C的三个牛奶桶,容量范围为1-20 ... -
USACO Section 1.4.3 [Arithmetic Progressions] Java题解
2011-07-15 16:38 1815题意分析: 定义算术级数:一种序列a, a+b, a+2b, ... -
USACO Section 1.4.2 [The Clocks] Java题解
2011-07-15 15:50 1929题意分析: 有编号为A-I的9个时钟,时钟只有指向3、6、9、 ... -
USACO Section 1.3.4 [Prime Cryptarithm] Java题解
2011-07-10 14:36 1416题意分析: 已知数字1-9组成集合的一个子集,求满足题意乘法步 ... -
USACO Section 1.3.3 [Calf Flac] Java题解
2011-07-10 14:35 1310题意分析: 一眼看上去,又是找对称的,不过有一些明显的干扰因素 ... -
USACO Section 1.3.2 [Barn Repair] Java题解
2011-07-10 14:33 1202题意分析: C头奶牛在畜栏里(一个畜栏里最多只能有一头奶牛), ... -
USACO Section 1.3.1 [Mixing Milk] Java题解
2011-07-10 14:30 935题意分析: 牛奶收购站每天需要收购总量为N加仑牛奶,告诉你每天 ... -
USACO Section 1.2.5 [Dual Palindromes] Java题解
2011-07-08 21:49 888题意分析: 这题和上一题基本是一样的,输出N个大于S的Dual ... -
USACO Section 1.2.4 [Palindromic Squares] Java题解
2011-07-08 21:43 980题意分析: N固定为10进制的1-300,N的平方表示成B进制 ... -
USACO Section 1.2.3 [Name That Number] Java题解
2011-07-08 21:40 1292题意分析: 奶牛们原来只有由四个数字组成的编号,例如4734, ... -
USACO Section 1.2.2 [Transformations] Java题解
2011-07-08 21:37 838题意分析: 给定N*N的二维数组的变化前和变化后的情况,思考如 ... -
USACO Section 1.2.1 [Milking Cows] Java题解
2011-07-07 15:39 1272题意分析: 输入为N组 [900,1800],[1200,22 ... -
USACO Section 1.1.4 [Broken Necklace] Java题解
2011-07-06 20:41 1284题意分析: 一串项链,由红蓝白三种颜色的珠子串成。在某一点拆开 ... -
USACO Section 1.1.3 [Friday the Thirteenth] Java题解
2011-07-04 20:22 806题意分析: 已知1900年1月1日是周一(即1900年1月13 ... -
USACO Section 1.1.2 [Greedy Gift Givers] Java题解
2011-07-04 12:31 1064解题思路: 直接用String[]保持名字的顺序,Map< ... -
USACO Section 1.1.1 [Your Ride Is Here] Java题解
2011-07-04 11:23 1600众所周知,Java的运行效率大约比C/C++慢3倍左右。大多数 ...
相关推荐
USACO所有题目的题解 NOCOW整理版
usaco测试数据+标程 usaco的section1到section5的所有测试数据 以及标准程序
USACO教程,包含USACO全部英文原题,题解(NOCOW整理版),翻译,教程,代码,测试数据。
适合USACO的Java选手参考
usaco的某道题的题解
USACO题解+代码+翻译,好东西,超级齐全,对大家帮助不小,特别是现在nocow挂了
我的USACO题解和程序
USACO1.4~2.3C语言题解 绝对能通过
USACO题解(NOCOW整理版).doc
Usaco总结&题解 一位大牛写的Usaco的总结,并有所有题的题解,推荐!!
usaco全部题解。 网址:blog.csdn.net/jiangshibiao
usaco section2.3--section5.5源程序。。。。。。。。。。。。。。。。
里面有usaco前几节的程序和代码,欢迎使用,希望对你有所帮主。
资源包包括USACO 2001-2007年月赛的测试数据;usaco月赛十年题典(2000-2009),usaco月赛2002-2008题解。单独下载需资源分30分以上。为了方便编程爱好者,我这边统一下载打包。欢迎下载。
丰富的USACO1.1--2.3.4的所有题解
USACO的偷懒程序
USACO题解及中文译题1.1.1-2.4.5 题目为TXT格式文档,代码为C++语言所编写
USACO月赛题解1
其中包含了USACO前些年的月赛试题和部分试题的数据,部分试题的详细题解,英文原题目与翻译后的题目,与题解一一对应
数据结构机考所参考的USACO网站所有题目的解题思路,资源比较稀有!