FZU OJ1401,终于搞定了

August 13, 2008 at 9:57 am ·20 views·Filed under ACM。。。···

耗时n小时，终于拿下了1401这个”死亡迷宫“。
令人欣慰的是，完成效率还不错，我耗时0.02s，呆哥耗时0.00s。
写了个解题报告，有兴趣可以看看。。。
If you enjoyed this post, make sure you subscribe to my RSS feed!

Comments

FZU OJ1401

August 11, 2008 at 10:30 am ·19 views·Filed under ACM。。。···

原题
给定一张图，图上有墙，有野怪，有血瓶等等，让你找到一条从起点东终点的路（100步以内），使得所剩能量与所走步数的比最大。
看了这题，第一感觉就是搜索。但是20*20的图，搜索起来，难免有些吃力。于是，考虑了一下动态规划，但是，似乎没有最优子结构，思考许久，还是回到了搜索。
搜索的话，因为有100步的限制，所以能截掉不少；另外，对每个点做些标记，应该截肢效果也不错。但是，毕竟4^100的数量级，还是很难应付。。。。
对于这题，暂时的做法还是如此，没有太好的想法。
If you enjoyed this post, make sure you subscribe to my RSS feed!

Comments

TOJ3006

August 8, 2008 at 10:00 am ·29 views·Filed under ACM。。。···

昨天偶然看见TOJ上挂有一个比赛，也就跟着做了会儿。

Comments

xiaonei App

August 6, 2008 at 7:27 pm ·34 views·Filed under Others （其他）···

最近心血来潮，想写个xiaonei app玩玩，大致想法如下：

每个玩家可以花一定数量的钱来构建 一个城市，一个城市里的每个建筑，也需花一定金额的RMB

Comments

厦大OJ 1051

August 5, 2008 at 10:12 pm ·37 views·Filed under ACM。。。···

题目大意：输入一个数N，求出N的组合，用它的公因数的次方表示出来。例如输入为5，起组合为5*4*3*2*1，输出应为2^3*3*5。这题主要难点在于N的取值最大可为1000000。而时间只有1s。

Comments

POJ 1837 Balance解题报告（动态规划）

August 5, 2008 at 4:47 pm ·56 views·Filed under ACM解题报告···

题目大意：
输入一个天平若干（<=20）挂钩的位置，将若干（<=20）砝码挂到天平上，问有多少种使天平挂平衡的方法。

解题思路：
用一个二维数组t[x][y+4000]记录挂x个砝码时到y这个值的方法数，将砝码一一挂上，最后记录所有砝码都挂上时的t[x][4000]的值，详见代码。

Comments

POJ 2917【数学题】

August 2, 2008 at 10:32 am ·45 views·Filed under ACM解题报告···

题目大意：
等式 1/x + 1/y = 1/n x,y,n都为正整数且x 给定n值，输出有多少对这样的x,y;
题意理解
此题主要是时间上要求很严格。不能直接用遍历（1/y = (x - n)/(x*n) 遍历判断x*n能否被（x - n）整除），这样时间不够用。

Comments

POJ1836【动态规划】

August 2, 2008 at 10:30 am ·46 views·Filed under ACM解题报告···

题目大意：
给出系列数字，要求求出一个最长串，使得任意一个数字都不在两个大于等于它的数字中间
题意理解
这题主要是要求一个不降序列和一个不升序列的序列，由此，可以看到跟2533（最长不降序列）很相像。实际上，也只要考虑几个小问题就行了。
解题思路：
在2533（最长不降序列）中，我们只要用一个1000的数组就行了。其状态转移方程为
F(K) = MAX(F(A1),F(A2)..F(Ai)) + 1,其中0== F(Ai)。即第K个数字及其之前数字的最长不降序列为其之前的某个小于它的数字的最长不降序列加一。
对于这题，则可用一个二维数组。其第一维与2533相同，储存其最长不降序列；第二维则储存最长不升序列。具体为：
F(K,0)=MAX(F(A1,0)…F(Ai,0)) + 1; F(K,1) = MAX(F(B1,0)..F(Bi,0),F(A1,1)..F(Bi,1)) + 1.
另外，还有一点需要注意，就是 5 5 5中间的5 的处理。。。

Comments

POJ3681[Finding the Rectangle]【枚举+限界】

August 2, 2008 at 10:26 am ·71 views·Filed under ACM解题报告···

【原题链接】
http://acm.pku.edu.cn/JudgeOnline/problem?id=3681
【题意描述】
给出N、M和N个点的坐标，要求找出面积最小的一个矩形，使其中至少包含M个点（恰处在边上的点不算包含在内）。

Comments

POJ2418【二叉搜索树】

July 21, 2008 at 10:33 pm ·73 views·Filed under ACM解题报告···

POJ2418【二叉搜索树】
题目描述：
Hardwood Species

Time Limit: 10000MS

Memory Limit: 65536K

Total Submissions: 3576

Accepted: 1421

Description
Hardwoodsare the botanical group of trees that have broad leaves, produce afruit or nut, and generally go dormant in the winter.
America’s temperate climates produce forests with hundreds ofhardwood species — trees that share certain biologicalcharacteristics. Although oak, maple and cherry all are types ofhardwood trees, for example, [...]

Comments