Dreams

04 2009 档案

 
hdu 1134 Game of Connections      摘要: Catalan Number(卡特兰数)
S(n) = C(2n,n)/(n+1)
递推公式:a(n)=((4*n-2)/(n+1))*a(n-1)
我不理解~  阅读全文
posted @ 2009-04-30 15:51 DreamSky 阅读(810) | 评论 (2)  编辑
hdu 1133 Buy the Ticket      摘要: 考虑(m+n)个人排队购票的情景,第(m+n)人站在第(m+n-1)个人的后面,则第(m+n )个人的排队方式可以由下列两种情况获得:
a.第(m+n )个人手持¥100的钞票,则在他之前的(m+(n-1))个人中有m个人手持¥50的钞票,有(n-1)个人手持¥100的钞票,此种情况共有f(m,n-1);
b.第(m+n )个人手持¥50的钞票,则在他之前的((m-1)+n)个人中有m-1个人手持¥50的钞票,有n个人手持¥100的钞票,此种情况共有f(m-1,n);
根据加法原理得到: f(m,n)=f(m-1,n)+f(m,n-1)
最终得到递推公式:f(m,n)= C(m+n,n)-C(m+n,m+1)
即:f(m,n) = ((m+1-n) / (m+1)) *((m+n)!)  阅读全文
posted @ 2009-04-30 15:36 DreamSky 阅读(884) | 评论 (0)  编辑
hutc 1042 Lecture Halls      摘要: nothing  阅读全文
posted @ 2009-04-29 08:10 DreamSky 阅读(262) | 评论 (0)  编辑
hutc 1041 最优装载      摘要: nothing  阅读全文
posted @ 2009-04-29 08:09 DreamSky 阅读(480) | 评论 (0)  编辑
hutc 1040 Knapsack Problem      摘要: nothing  阅读全文
posted @ 2009-04-29 08:07 DreamSky 阅读(295) | 评论 (0)  编辑
vijos 1313 金明的预算方案      摘要: 背包如此之妙(有依赖的背包)
题目大意:给你一系列物品清单,其中两物品直接可能存在主附关系,即要买附件必须将其附件也买下,比如若桌子跟椅子是主附关系,那么想买椅子则必须桌子也买下……问题来了,给你钱N,物品若干,快快买吧……如何买?
dp[j]表示钱为j的时候买得东西的最大价值
一、当物品为主件时:
1、没有附件
MAX(不买,买主件)
2、有一个附件
MAX(不买,只买主件,买主件与一附件)
3、有两个附件
MAX(不买,只买主件,买主件与一附件,买主件与两附件)
二、当物品为附件时:直接跳过
  阅读全文
posted @ 2009-04-27 17:41 DreamSky 阅读(499) | 评论 (0)  编辑
vijos 1133 装箱问题      摘要: 温习背包
  阅读全文
posted @ 2009-04-27 14:23 DreamSky 阅读(300) | 评论 (0)  编辑
vijos 1317 开心的金明      摘要: 比较明显的DP
稍稍多了一个条件,细细品味  阅读全文
posted @ 2009-04-27 13:56 DreamSky 阅读(246) | 评论 (0)  编辑
hdu 2670 Girl Love Value      摘要: 女孩的爱不易得~
先对损耗值从大到小排序,使损失最小化,然后再常规化DP
dp[i][j] = MAX(dp[i-1][j] , dp[i-1][j-1] + X)//dp[i][j] 表示前i个人中选j个的最优值  阅读全文
posted @ 2009-04-26 20:09 DreamSky 阅读(358) | 评论 (1)  编辑
hdu 1074 Doing Homework      摘要: 还需要慢慢揣摩~
貌似用的记忆法搜索~  阅读全文
posted @ 2009-04-26 19:30 DreamSky 阅读(1338) | 评论 (1)  编辑
hdu 2059 龟兔赛跑      摘要: 无言  阅读全文
posted @ 2009-04-26 18:51 DreamSky 阅读(644) | 评论 (0)  编辑
hdu 1114 Piggy-Bank      摘要: 完全背包
时间从546MS优化到93MS,感觉不容易,呵呵~
还需要慢慢消化~  阅读全文
posted @ 2009-04-25 20:22 DreamSky 阅读(829) | 评论 (1)  编辑
hdu 2152 Fruit      摘要: 最后一道母函数
G(X,Y,Z…)=(X^i…X^j)*(Y^i…Y^j)*(Z^i…Z^j)*……  阅读全文
posted @ 2009-04-25 10:59 DreamSky 阅读(549) | 评论 (2)  编辑
hdu 2069 Coin Change      摘要: 母函数,终于貌似理解一点了~继续努力吧
ans[i][j]表示i分钱用j个硬币组合的方案数
要求记录组合硬币的个数~值得一看
注意点:1. 要求 0 cent 输出 1
2. 如果 硬币总数超过100,是不合法的,也就是不用计算超过100个硬币的找钱方法.  阅读全文
posted @ 2009-04-25 10:33 DreamSky 阅读(1341) | 评论 (5)  编辑
hdu 1709 The Balance      摘要: 题目大意:天平平衡问题,给你n个砝码,每个砝码质量Wi,判断有多少种质量不能称量,质量范围是所以砝码的质量和
当然啦,天平两边都是可以放砝码的  阅读全文
posted @ 2009-04-25 09:18 DreamSky 阅读(373) | 评论 (0)  编辑
va家族的等级制      摘要: 先求出一段串是否为回文~
再是单调子序列思想~  阅读全文
posted @ 2009-04-24 21:52 DreamSky 阅读(218) | 评论 (0)  编辑
hdu 1171 Big Event in HDU      摘要: 母函数解决
DP算法还是想不出来
郁闷中……  阅读全文
posted @ 2009-04-24 18:11 DreamSky 阅读(1774) | 评论 (9)  编辑
hdu 1085 Holding Bin-Laden Captive!      摘要: 继续母函数
G(X)=(1+X+X^2+X^3+……)*(1+X^2+X^4+……)*(1+X^5+X^10+……)
时间不太好~  阅读全文
posted @ 2009-04-24 16:42 DreamSky 阅读(672) | 评论 (3)  编辑
hdu 1028 Ignatius and the Princess III      摘要: 再来一次母函数~
G(X)=(1+X+X^2+X^3+……)*(1+X^2+X^4+……)  阅读全文
posted @ 2009-04-24 14:55 DreamSky 阅读(585) | 评论 (1)  编辑
hdu 1398 Square Coins      摘要: 还不是很理解~
母函数G(X)=(1+X+X^2+X^3+……+X^289) *(1+X^4+X^8+X^12+……+X^288)*(1+X^9+X^18+X^27+……+X^288)*……*(1+X^289);
  阅读全文
posted @ 2009-04-24 14:23 DreamSky 阅读(516) | 评论 (1)  编辑
hdu 1728 逃离迷宫      摘要: 一次性走完一行(一列)
该题用DFS超时了,不会剪枝~5555555  阅读全文
posted @ 2009-04-23 19:25 DreamSky 阅读(1418) | 评论 (0)  编辑
zju 3182 Nine Interlinks      摘要: 找规律  阅读全文
posted @ 2009-04-23 08:05 DreamSky 阅读(247) | 评论 (0)  编辑
Lecture Halls (会议安排)      摘要: 贪心+优先队列  阅读全文
posted @ 2009-04-22 13:31 DreamSky 阅读(380) | 评论 (0)  编辑
hdu 2512 一卡通大冒险      摘要: 内存消耗比较大~
什么类型的DP没想清楚,dp[i][j]表示i张卡片分成j堆时的情况数,
dp[i][j] = dp[i-1][j] * j + dp[i-1][j-1](dp[i-1][j] * j 表示i-1张卡片分为j堆的时候,第i张卡片可以分到任意一堆中,当然也就出现了一种新的分堆方法,dp[i-1][j-1]表示第i张卡片要独立成为一堆时的方案数)   阅读全文
posted @ 2009-04-20 16:38 DreamSky 阅读(305) | 评论 (0)  编辑
hdu 2182 Frog      摘要: 青蛙吃害虫~
跟龟兔赛跑比较类似,第i个位置的值跟其前面位置的值有关  阅读全文
posted @ 2009-04-17 22:10 DreamSky 阅读(362) | 评论 (0)  编辑
hdu 2275 Kiki & Little Kiki 1      摘要: set容器的应用
身旁有牛人就是好~  阅读全文
posted @ 2009-04-17 18:33 DreamSky 阅读(292) | 评论 (0)  编辑
NK 1137 (hutc 1036)Pebble Merging(石子合并问题)      摘要: 石子合并~
使用了最笨的方法,利用矩阵连乘思想  阅读全文
posted @ 2009-04-17 13:05 DreamSky 阅读(450) | 评论 (0)  编辑
zju 2849 Attack of Panda Virus      摘要: 熊猫烧香 优先队列+BFS  阅读全文
posted @ 2009-04-17 09:15 DreamSky 阅读(746) | 评论 (0)  编辑
hdu 1016 Prime Ring Problem      摘要: 简单深搜~  阅读全文
posted @ 2009-04-16 16:51 DreamSky 阅读(634) | 评论 (0)  编辑
hutc 1035 编辑距离问题      摘要: 题目大意:串变换,有串s最少经过多少步能够变换成t串
先用DFS过了,(但在南开JudgeOnline超时 555555555……)
再一次DP,总算都过了  阅读全文
posted @ 2009-04-16 14:37 DreamSky 阅读(582) | 评论 (0)  编辑
zju 1234 Chopsticks      摘要: 题目大意:从n根筷子当中选取j对,其中一对筷子包含三根,并且要求第三跟不短语前两根。要求取出的筷子长度差(前两根的长度差)的平方的和最小。
num[i] 表示第i+1个筷子与第i个筷子长度差的平方~

开始从前面往后推,漏洞百出:dp[i][j]表示从1……i个筷子中选取j对,
dp[i][j] = MIN(dp[i-1][j],dp[i-3][j-1] + num[i-2]);
问题在哪? 第i个筷子能用,
一种情况:第i-1个筷子能与第i-2个筷子配对了(来了第三根筷子i);
二种情况:影响1……i-1个筷子中取j对筷子的配对情况。WHY?think about~

最后从后往前推:dp[i][j]表示从i……n个筷子中选取j对,
dp[i][j] = MIN(dp[i+1][j],dp[i+2][j-1] + num[i]);
没问题了吧~ 第i个筷子取,则必与第i+1个筷子配对,不取则可以忽略它(就因为它是当前最短的)  阅读全文
posted @ 2009-04-16 10:04 DreamSky 阅读(350) | 评论 (0)  编辑
hdu 1026 Ignatius and the Princess I      摘要: BFS+保存路径
可以试想一下从终点走点始点,这样路径是否好处理一点~  阅读全文
posted @ 2009-04-16 07:58 DreamSky 阅读(936) | 评论 (0)  编辑
hdu 1421 搬寝室      摘要: 搬寝室——从n个物品中选取k对,使得每对物品质量差的平方之和最小
赋初值的时候要小心~
dp[i][j]表示从前i个物品中选取j对物品的最优值,
dp[i][j]=MIN(dp[i-1][j],dp[i-2][j-1]+(w[i] - w[i-1])*(w[i] - w[i-1])),
取第i个物品,则必取第i-1个物品,WHY?相连物品平方差必定最小~
在WXH帮助下完成,学习学习~  阅读全文
posted @ 2009-04-15 19:01 DreamSky 阅读(603) | 评论 (0)  编辑
并查集的初级应用及进阶      摘要: 并查集资料
拷贝牛人http://blog.csdn.net/pure_life/archive/2008/09/13/2922118.aspx  阅读全文
posted @ 2009-04-15 13:46 DreamSky 阅读(456) | 评论 (0)  编辑
hdu 1159 Common Subsequence      摘要: 重温最长公共子串(LCS)
~  阅读全文
posted @ 2009-04-15 13:16 DreamSky 阅读(457) | 评论 (0)  编辑
hdu 1558 Segment set      摘要: 题目大意:求交叉在一起的线段的条数,如果线段A连接着另外两条不相交线段B、C,则认为B、C也是相交的
简而言之就是输出要查找的线段所在集合中线段数为多少~
主要参考了牛人的代码,寻求了很久才找到一个能正确判断两线段是否相交的函数,珍惜珍惜~
并查集中的路径压缩,就这么回事~  阅读全文
posted @ 2009-04-14 20:22 DreamSky 阅读(503) | 评论 (0)  编辑
hdu 1272 小希的迷宫      摘要: 小希的迷宫~
题意:要求无回路,同属于一个集合
注意 输入数据 0 0 的情况,应该输出 Yes~
并查集判连通,未输入的结点不用考虑,用visited数组标志结点是否出现过
矮树并入高树 有益于 查找  阅读全文
posted @ 2009-04-12 17:08 DreamSky 阅读(1030) | 评论 (1)  编辑
hdu 1232 畅通工程      摘要: 并查集好不简单,哎~笨牛~
不过在学弟的耐心指导下还是解决了,也算是跨进了并查集的门槛吧……
核心问题:求出有多少个集合~  阅读全文
posted @ 2009-04-12 11:34 DreamSky 阅读(566) | 评论 (3)  编辑
hdu 2141 Can you find it?      摘要: 该题很容易超时,提交20余次~ 很郁闷~
先列举序列a与序列b的和,然后再进行二分查找
for(i=0 ; i< lena; i++)
for(j=0 ; j< lenb; j++)
temp[k++] = a[i] + b[j];  阅读全文
posted @ 2009-04-11 19:56 DreamSky 阅读(426) | 评论 (0)  编辑
hdu 1239 Calling Extraterrestrial Intelligence Again      摘要: 典型的搜索
题目大意:给出三个整数m a b 其中 4 < m <= 100000 , 1 <= a <= b <= 1000,寻找一对素数p q 使得
p*q<=m && a/b <= p/q <=1 ,要求使p*q尽可能大
按常规思想,数据量大肯定超时~
如果q为某个大于10000的素数,那么当p<10时,p/q < 0.001(然而a/b>=0.01),当p>10时,p*q>100000(然而m<=100000)
因此 p q 都是在10000以内的素数~
剪枝:if ( a[j]>m || a[j]*a[i]>m || ( (double)a[i]/a[j])more~   阅读全文
posted @ 2009-04-11 19:44 DreamSky 阅读(431) | 评论 (0)  编辑
hdu 1010 Tempter of the Bone      摘要: 走迷宫-主要考查奇偶剪枝法
题目大意:给出起始位置,然后给定时间T,在时间T内从出发点走到终点,每步只能往上、下、左、右四个方向走一步,时间是1,不能在原地停留。如果到达某点的剩余时间为奇数,那么必定是在奇数步内走到终点,也就是两点的 行差绝对值 + 列差绝对值 也要是奇数~ 奇偶剪枝  阅读全文
posted @ 2009-04-11 19:26 DreamSky 阅读(840) | 评论 (1)  编辑
hdu 1072 Nightmare      摘要: 做噩梦了~
逃了好久好久~
在炸弹爆炸之前逃出迷宫,定时炸弹时间可以重置~
mark[i][j]表示第i行j列位置时剩余爆炸时间,当然是时间越长越好  阅读全文
posted @ 2009-04-11 19:15 DreamSky 阅读(699) | 评论 (0)  编辑
zju 1558 Euro Efficiency      摘要: 在六种欧元面值中找零……
  阅读全文
posted @ 2009-04-10 20:45 DreamSky 阅读(246) | 评论 (0)  编辑
hdu 1298 T9      摘要: 字典树+dfs+剪枝
先理解题意,给你一连串数字,输出其对应的出现频率最大的单词
在每一步深搜之前先做剪枝~  阅读全文
posted @ 2009-04-10 16:03 DreamSky 阅读(753) | 评论 (2)  编辑
hdu 1075 What Are You Talking About      摘要: Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 102400/204800 K (Java/Others)
Total Submission(s): 1238 Accepted Submission(s): 340
先用map勉强过了(1593MS 37528K)~
然后再建字典树(296MS 59804K)~  阅读全文
posted @ 2009-04-09 17:43 DreamSky 阅读(970) | 评论 (8)  编辑
hdu 1251 统计难题      摘要: 还是构建字典树~  阅读全文
posted @ 2009-04-09 14:17 DreamSky 阅读(364) | 评论 (0)  编辑
hdu 1800 Flying to the Mars      摘要: 利用字典树统计数字出现次数,输出出现次数最多的一次。
注意因为是大数,故需考虑除去前缀0,因0010 、010是同一个数字

字典树:又称为Trie,是一种用于快速检索的多叉树结构。Trie把要查找的关键词看作一个字符序列,并根据构成关键词字符的先后顺序构造用于检索的树结构;一棵m度的Trie树或者为空,或者由m棵m度的Trie树构成。
特别地:和二叉查找树不同,在Trie树中,每个结点上并非存储一个元素。   阅读全文
posted @ 2009-04-09 14:15 DreamSky 阅读(436) | 评论 (0)  编辑
Tian Ji -- The Horse Racing      摘要: 田忌赛马  阅读全文
posted @ 2009-04-08 19:28 DreamSky 阅读(295) | 评论 (0)  编辑
hdu 1195 Open the Lock      摘要: 对每个数字只要三种转换状态:加1,减1,跟其后面一个数字交换位置。
需注意的是最后一个数字没有交换,数字9加1变为1,数字1减1变为9。
很传统的一个BFS……
利用hash表标志走过的状态……  阅读全文
posted @ 2009-04-08 10:04 DreamSky 阅读(332) | 评论 (0)  编辑
hdu 1050 Moving Tables      摘要: 最少拦劫子系统类似  阅读全文
posted @ 2009-04-07 16:28 DreamSky 阅读(523) | 评论 (0)  编辑
hdu 1013 Digital Roots      摘要: 开始用int,WA,接着用__int64,还是WA,最后改用字符数组,新的错误:Compilation Error, WHY?
C语言要求变量的定义应该放在所有的执行语句之前,而C++则放松了限制,只要求在第一次使用该变量之前进行定义即可……
切记切记……
看下面代码————焕然大悟!!!  阅读全文
posted @ 2009-04-04 10:49 DreamSky 阅读(735) | 评论 (0)  编辑
hdu 1142 A Walk Through the Forest      摘要: 记忆法搜索
因为1是出发点,2是终点,先运用dijkstra(迪杰斯特拉)算法计算出所有点到终点的最短路径。
然后记忆法搜索,从1开始,与1相连且到终点2的距离比dist[1]小的点都可行,依此类推……  阅读全文
posted @ 2009-04-03 20:27 DreamSky 阅读(988) | 评论 (1)  编辑
hdu 2066 一个人的旅行      摘要: 多旅行多快乐  阅读全文
posted @ 2009-04-03 19:23 DreamSky 阅读(782) | 评论 (1)  编辑
zju 1076 Gene Assembly      摘要: 简单贪心
类似活动安排问题  阅读全文
posted @ 2009-04-03 19:14 DreamSky 阅读(237) | 评论 (0)  编辑
hdu 1078 FatMouse and Cheese      摘要: 米老鼠觅食
从坐标0、0出发,依次找其周围最优的方案然后递归下去,同时记录搜索过的地方  阅读全文
posted @ 2009-04-03 08:46 DreamSky 阅读(257) | 评论 (0)  编辑
poj 1088 滑雪      摘要: 滑雪不好玩  阅读全文
posted @ 2009-04-02 20:20 DreamSky 阅读(156) | 评论 (0)  编辑
zju 2022 Factorial      摘要: 计算N!后面零的个数  阅读全文
posted @ 2009-04-02 12:28 DreamSky 阅读(258) | 评论 (0)  编辑
zju 1199 Point of Intersection      摘要: 公式推导过程
temp=(y1-y2)/(x1-x2);
sqrt((x1-x0)*(x1-x0)+(y1-y0)*(y1-y0))/sqrt((x1-x0)*(x1-x0)+(y1-y0)*(y1-y0))=r1/r2;
(y1-y0)/(x1-x0)=temp;
(y2-y0)/(x2-x0)=temp;
  阅读全文
posted @ 2009-04-02 09:37 DreamSky 阅读(165) | 评论 (0)  编辑
zju 1047 Image Perimeters      摘要: 求X块图的面积
从出发点向四周扩散,如果X的一边为.或者是边界,则sum++  阅读全文
posted @ 2009-04-01 21:31 DreamSky 阅读(247) | 评论 (0)  编辑
zju 3049 Diablo II Items      摘要: 题目的背景是鼎鼎大名的暗黑2,这题讲的是关于暗黑卖物品的一个问题。暗黑里面有两种物品,普通物品和魔法
物品。普通物品只有一个普通出售价格,而魔法物品有两个出售价格,鉴定前的价格和鉴定后的价格,用鉴定卷轴
鉴定魔法物品,物品的价格就变成鉴定后价格了。然后现在没有钱,有一堆物品要卖,其中有若干的普通物品和若
干的魔法物品,其中魔法物品都是没有鉴定过的。同时,可以买无限量的鉴定卷轴(价格cost)。现在的问题是怎么
卖东西才能让最后的总收益最大。这题主要考察的是分析题目的能力。首先发现,所有的普通物品可以直接卖掉,
因为他们只有一个价格。然后考察魔法物品(鉴定前价格normalPrice,鉴定后价格magicPrice),如果
normalPrice >= magicPrice - cost,那么也可以把它们当作普通物品一样直接卖了,因为鉴定它们完全不会有任
何的收获。然后,剩下的物品,鉴定后卖总是比不鉴定直接卖要赚钱的。我们可以发现,一旦我们有钱可以买得起
一个鉴定卷轴,买一个来鉴定一个魔法物品然后卖掉后,钱会增加,于是可以继  阅读全文
posted @ 2009-04-01 12:22 DreamSky 阅读(249) | 评论 (1)  编辑
 

 
<2009年3月>
日一二三四五六
22232425262728
1234567
891011121314
15161718192021
22232425262728
2930311234

 公告


 导航

  • C++博客
  • 首页
  • 发新随笔
  • 发新文章
  • 联系
  • 聚合
  • 管理

 统计

  • 随笔: 84
  • 文章: 7
  • 评论: 49
  • 引用: 0

常用链接

  • 我的随笔
  • 我的评论
  • 我参与的随笔

留言簿(6)

  • 给我留言
  • 查看公开留言
  • 查看私人留言

随笔分类

  • asp相关(3) (rss)
  • BFS(8) (rss)
  • DFS(7) (rss)
  • DP(27) (rss)
  • greedy(9) (rss)
  • LG(4) (rss)
  • Math(7) (rss)
  • Others(6) (rss)
  • 并查集(4) (rss)
  • 母函数(7) (rss)
  • 线段树 (rss)
  • 字典树(4) (rss)

随笔档案

  • 2009年8月 (3)
  • 2009年5月 (17)
  • 2009年4月 (60)
  • 2009年3月 (4)

文章分类

  • 创作(1) (rss)
  • 随感(5) (rss)
  • 文学(1) (rss)

文章档案

  • 2010年12月 (1)
  • 2010年8月 (1)
  • 2009年8月 (1)
  • 2009年5月 (1)
  • 2009年4月 (3)

相册

  • 乌镇
  • 原野天地

百事百通

  • analogy_翻译_爱词霸在线词典
  • bia菜
  • CSS学习资料
  • DB
  • Feng
  • Happy峰
  • Wpl
  • Xredman
  • 百度
  • 北大ACM
  • 福建师范大学ACM
  • 谷歌
  • 果树伯伯
  • 杭电ACM
  • 湖州师范学院主页
  • 精品笑话
  • 绿色软件
  • 史艳婷
  • 霜天晓角
  • 天津大学ACM
  • 厦门大学ACM
  • 信息学竞赛
  • 这是什么
  • 浙大ACM
  • 浙江工商大学ACM
  • 浙江工业大学ACM
  • 浙江林学院ACM

搜索

  •  

积分与排名

  • 积分 - 47286
  • 排名 - 473

最新评论

  • 1. re: hdu 1074 Doing Homework
  • 评论内容较长,点击标题查看
  • --guo

阅读排行榜

  • 1. hdu 1171 Big Event in HDU(1774)

评论排行榜

  • 1. hdu 1171 Big Event in HDU(9)

Powered by: 博客园
模板提供:沪江博客
Copyright ©2025 DreamSky