DP - Dreams - C++博客

hdu 2372 El Dorado 摘要: 注意大数，需要用__int64 阅读全文

posted @ 2009-05-14 19:49 DreamSky 阅读(476) | 评论 (0) 编辑

01-package 摘要: 背包问题阅读全文

posted @ 2009-05-08 21:48 DreamSky 阅读(526) | 评论 (0) 编辑

zju 1883 Tight Words 摘要: 根本没考虑什么大数~ 阅读全文

posted @ 2009-05-08 15:24 DreamSky 阅读(369) | 评论 (0) 编辑

zju 3201 Tree of Tree 摘要: Tree_DP
抄袭大牛的~ 阅读全文

posted @ 2009-05-07 14:36 DreamSky 阅读(289) | 评论 (0) 编辑

zju 2852 Deck of Cards 摘要: 注意点：每张card放下时优先考虑是否能恰好组成21点，再做下一步
dp问题都是从最优子结构出发，拓展思维阅读全文

posted @ 2009-05-06 08:48 DreamSky 阅读(322) | 评论 (0) 编辑

hdu 2191 悼念512汶川大地震遇难同胞——珍惜现在，感恩生活摘要: 温习背包~ 阅读全文

posted @ 2009-05-04 20:49 DreamSky 阅读(644) | 评论 (0) 编辑

hdu 2765 Recursively Palindromic Partitions 摘要: 加数顺序为回文串形式~同时其前半部与后半部也为回文串形式阅读全文

posted @ 2009-05-02 18:58 DreamSky 阅读(283) | 评论 (0) 编辑

vijos 1313 金明的预算方案摘要: 背包如此之妙（有依赖的背包）
题目大意：给你一系列物品清单，其中两物品直接可能存在主附关系，即要买附件必须将其附件也买下，比如若桌子跟椅子是主附关系，那么想买椅子则必须桌子也买下……问题来了，给你钱N，物品若干，快快买吧……如何买？
dp[j]表示钱为j的时候买得东西的最大价值
一、当物品为主件时：
1、没有附件
MAX（不买，买主件）
2、有一个附件
MAX（不买，只买主件，买主件与一附件）
3、有两个附件
MAX（不买，只买主件，买主件与一附件，买主件与两附件）
二、当物品为附件时：直接跳过
阅读全文

posted @ 2009-04-27 17:41 DreamSky 阅读(489) | 评论 (0) 编辑

vijos 1133 装箱问题摘要: 温习背包
阅读全文

posted @ 2009-04-27 14:23 DreamSky 阅读(292) | 评论 (0) 编辑

vijos 1317 开心的金明摘要: 比较明显的DP
稍稍多了一个条件，细细品味阅读全文

posted @ 2009-04-27 13:56 DreamSky 阅读(240) | 评论 (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 阅读(345) | 评论 (1) 编辑

hdu 1074 Doing Homework 摘要: 还需要慢慢揣摩~
貌似用的记忆法搜索~ 阅读全文

posted @ 2009-04-26 19:30 DreamSky 阅读(1317) | 评论 (1) 编辑

hdu 2059 龟兔赛跑摘要: 无言阅读全文

posted @ 2009-04-26 18:51 DreamSky 阅读(634) | 评论 (0) 编辑

hdu 1114 Piggy-Bank 摘要: 完全背包
时间从546MS优化到93MS，感觉不容易，呵呵~
还需要慢慢消化~ 阅读全文

posted @ 2009-04-25 20:22 DreamSky 阅读(820) | 评论 (1) 编辑

va家族的等级制摘要: 先求出一段串是否为回文~
再是单调子序列思想~ 阅读全文

posted @ 2009-04-24 21:52 DreamSky 阅读(210) | 评论 (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 阅读(296) | 评论 (0) 编辑

hdu 2182 Frog 摘要: 青蛙吃害虫~
跟龟兔赛跑比较类似，第i个位置的值跟其前面位置的值有关阅读全文

posted @ 2009-04-17 22:10 DreamSky 阅读(349) | 评论 (0) 编辑

NK 1137 （hutc 1036）Pebble Merging（石子合并问题）摘要: 石子合并~
使用了最笨的方法，利用矩阵连乘思想阅读全文

posted @ 2009-04-17 13:05 DreamSky 阅读(442) | 评论 (0) 编辑

hutc 1035 编辑距离问题摘要: 题目大意：串变换，有串s最少经过多少步能够变换成t串
先用DFS过了，（但在南开JudgeOnline超时 555555555……）
再一次DP，总算都过了阅读全文

posted @ 2009-04-16 14:37 DreamSky 阅读(574) | 评论 (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 阅读(340) | 评论 (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 阅读(596) | 评论 (0) 编辑

hdu 1159 Common Subsequence 摘要: 重温最长公共子串（LCS）
~ 阅读全文

posted @ 2009-04-15 13:16 DreamSky 阅读(450) | 评论 (0) 编辑

zju 1558 Euro Efficiency 摘要: 在六种欧元面值中找零……
阅读全文

posted @ 2009-04-10 20:45 DreamSky 阅读(235) | 评论 (0) 编辑

hdu 1078 FatMouse and Cheese 摘要: 米老鼠觅食
从坐标0、0出发，依次找其周围最优的方案然后递归下去，同时记录搜索过的地方阅读全文

posted @ 2009-04-03 08:46 DreamSky 阅读(252) | 评论 (0) 编辑

zju 3049 Diablo II Items 摘要: 题目的背景是鼎鼎大名的暗黑2，这题讲的是关于暗黑卖物品的一个问题。暗黑里面有两种物品，普通物品和魔法
物品。普通物品只有一个普通出售价格，而魔法物品有两个出售价格，鉴定前的价格和鉴定后的价格，用鉴定卷轴
鉴定魔法物品，物品的价格就变成鉴定后价格了。然后现在没有钱，有一堆物品要卖，其中有若干的普通物品和若
干的魔法物品，其中魔法物品都是没有鉴定过的。同时，可以买无限量的鉴定卷轴（价格cost）。现在的问题是怎么
卖东西才能让最后的总收益最大。这题主要考察的是分析题目的能力。首先发现，所有的普通物品可以直接卖掉，
因为他们只有一个价格。然后考察魔法物品（鉴定前价格normalPrice，鉴定后价格magicPrice），如果
normalPrice >= magicPrice - cost，那么也可以把它们当作普通物品一样直接卖了，因为鉴定它们完全不会有任
何的收获。然后，剩下的物品，鉴定后卖总是比不鉴定直接卖要赚钱的。我们可以发现，一旦我们有钱可以买得起
一个鉴定卷轴，买一个来鉴定一个魔法物品然后卖掉后，钱会增加，于是可以继阅读全文

posted @ 2009-04-01 12:22 DreamSky 阅读(236) | 评论 (1) 编辑

zju 2975 Kinds of Fuwas 摘要: 时间复度不好，请高手赐教！阅读全文

posted @ 2009-03-31 18:49 DreamSky 阅读(361) | 评论 (1) 编辑

El Dorado 摘要: 理解dp[i][j]的意思阅读全文

posted @ 2009-03-31 15:57 DreamSky 阅读(142) | 评论 (0) 编辑

DP

公告

导航

统计

常用链接

留言簿(6)

随笔分类

随笔档案

文章分类

文章档案

相册

百事百通

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜