动态规划

• [动态规划]O(n^2 / logn)的LCS      摘要: 上次说，LCS有O(n^2 / logn)的解法。这个解法是在字符集不大的情况下，先预处理，再用位运算做状态转移。
  唐文斌曾经翻译过一篇论文，专门讨论这个问题。
  
  下面是练习题（n = 10000 的LCS）
  http://acm.whu.edu.cn/oak/problem/problem.jsp?problem_id=1210
  
  和我的解答
  
    阅读全文
  posted @ 2007-10-19 16:56 Felicia 阅读(1351) | 评论 (5)  编辑
• [动态规划] pku1458 最长公共子序列      摘要: 最长公共子序列……想必很多人都知道吧……
  这里给出一个O(n^2)的算法，人人都会的。
  但是，我想说，我所知道的最好算法，是O(n^2 / logn)的。
  
    阅读全文
  posted @ 2007-10-16 22:46 Felicia 阅读(1403) | 评论 (4)  编辑
• [动态规划]pku1080      摘要: 很简单的DP，也是很基础的DP。做法就不说啦：）
  
    阅读全文
  posted @ 2007-10-12 22:25 Felicia 阅读(1098) | 评论 (1)  编辑
• [动态规划]pku1338      摘要: 非常经典的递推计算。基本思想是设3个指针，分别表示3个素数乘到哪了，然后通过比较3个指针位置的递推结果来确定下一个数是什么。
  具体实现见代码。
  
    阅读全文
  posted @ 2007-10-09 21:53 Felicia 阅读(800) | 评论 (1)  编辑
• [动态规划]pku3420      摘要: 经典题型。如果列数较少，就能用我们熟知的状态压缩DP解决。但现在列数有2^31。考虑到相邻两列之间状态转移规则是相同的，我们可以用矩阵表示这种转移规则，而最后的结果就是求这个转移矩阵的n次幂的左上角元素。
  
    阅读全文
  posted @ 2007-10-08 09:19 Felicia 阅读(1094) | 评论 (0)  编辑
• [动态规划]pku1191      摘要: 不错的DP题。状态f[i][x1][y1][x2][y2]表示要把(x1,y1) -- (x2, y2) 分割成i块所得到的最小平方和（平方和指的是每块矩形的和的平方和）。然后根据水平和竖直切割进行状态转移。这样计算出f[n][1][1][8][8]得到整个棋盘分割成n块得到的最小平方和，然后代入均方差公式算得结果。
  
    阅读全文
  posted @ 2007-10-08 09:12 Felicia 阅读(794) | 评论 (1)  编辑
• [动态规划]pku1179      摘要: 经典的DP，把环断开，f[i][j][0]记录i到j的最小值，f[i][j][1]记录最大值，然后递推计算。记录最小值是因为两个负数乘起来可能得到一个大的正数。
  
    阅读全文
  posted @ 2007-10-05 16:47 Felicia 阅读(604) | 评论 (0)  编辑
• [动态规划]pku1189      摘要: 概率+DP，比较经典的题。按照递推的方式计算概率。
  
    阅读全文
  posted @ 2007-10-04 20:47 Felicia 阅读(787) | 评论 (4)  编辑
• [动态规划]pku1185      摘要: 经典的状态压缩DP，状态是f[i][j]，表示第i行，以3进制j为状态。j的位代表一个格子，只能是：0表示第i行和第i - 1行都没有炮兵，1表示第i行没有炮兵而第i-1行有炮兵，2表示第i行有炮兵。然后用DFS进行状态转移。一开始我做了超时，后来预处理了一下合法状态，快了不少，才AC。
  
    阅读全文
  posted @ 2007-09-30 22:09 Felicia 阅读(1042) | 评论 (0)  编辑
• [动态规划]pku1163      摘要: 今天郁闷了，贴个小代码
  
    阅读全文
  posted @ 2007-09-29 22:43 Felicia 阅读(539) | 评论 (0)  编辑
• [动态规划]动态规划总结 by Amber      摘要: 动态规划总结 by Amber
  
    阅读全文
  posted @ 2007-09-29 20:25 Felicia 阅读(3948) | 评论 (0)  编辑
• [动态规划]pku3133      摘要: 强烈推荐此题！
  状态压缩DP的好题！
  分析见内
  
    阅读全文
  posted @ 2007-09-24 21:12 Felicia 阅读(1141) | 评论 (4)  编辑
• [动态规划]pku1038      摘要: 经典的状态压缩DP，《算法艺术与信息学竞赛》的例题。f[i][j]表示前i行，最后两行状态为二进制数j，嵌入的最多芯片数。第i行到第i+1行用DFS进行状态转移。
  由于第i+1行只和第i行有关，故可以用滚动数组优化。
  
    阅读全文
  posted @ 2007-09-12 20:44 Felicia 阅读(1530) | 评论 (3)  编辑
• [动态规划]pku3375      摘要: A O(NM) dynamic programming algorithm is quite apparent after sorting the computers and network interfaces by their coordinates. Furthermore, in any optimized case, for each computer the difference between the the indices of the network interfaces matching to and closest to the computer is never larger than N. So the complexity could be reduced to O(N2)
  
  有很多细节不好考虑，应该是我的水平原因。最后我向updog要了数据才过的。而且代码写的不好。将就看一下吧。
  
    阅读全文
  posted @ 2007-09-11 22:28 Felicia 阅读(799) | 评论 (1)  编辑
• [动态规划]pku1170      摘要: 呼~今天去学校啦！早上7点起床写题，挑了个简单题写 ^_^
  这个是IOI95的DP题。用一个b位的6进制数i表示状态。这个6进制数的每一位分别表示相应物品的数量。f[i]表示状态i下的最小花费。同样也可以用6进制数j表示优惠。那么，f[i]就能转移到f[i - j]，如果优惠j可用的话。代价是使用优惠j时减少的花费。最后的答案就是min(f[i])，0 <= i <= start（start是初始状态）。
  
    阅读全文
  posted @ 2007-09-04 08:37 Felicia 阅读(668) | 评论 (0)  编辑

Full 动态规划 Archive