动态规划

• [动态规划]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 阅读(1348) | 评论 (5)  编辑
• [动态规划] pku1458 最长公共子序列      摘要: 最长公共子序列……想必很多人都知道吧……
  这里给出一个O(n^2)的算法，人人都会的。
  但是，我想说，我所知道的最好算法，是O(n^2 / logn)的。
  
    阅读全文
  posted @ 2007-10-16 22:46 Felicia 阅读(1397) | 评论 (4)  编辑
• [动态规划]pku1080      摘要: 很简单的DP，也是很基础的DP。做法就不说啦：）
  
    阅读全文
  posted @ 2007-10-12 22:25 Felicia 阅读(1096) | 评论 (1)  编辑
• [动态规划]pku1338      摘要: 非常经典的递推计算。基本思想是设3个指针，分别表示3个素数乘到哪了，然后通过比较3个指针位置的递推结果来确定下一个数是什么。
  具体实现见代码。
  
    阅读全文
  posted @ 2007-10-09 21:53 Felicia 阅读(798) | 评论 (1)  编辑
• [动态规划]pku3420      摘要: 经典题型。如果列数较少，就能用我们熟知的状态压缩DP解决。但现在列数有2^31。考虑到相邻两列之间状态转移规则是相同的，我们可以用矩阵表示这种转移规则，而最后的结果就是求这个转移矩阵的n次幂的左上角元素。
  
    阅读全文
  posted @ 2007-10-08 09:19 Felicia 阅读(1090) | 评论 (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 阅读(792) | 评论 (1)  编辑
• [动态规划]pku1179      摘要: 经典的DP，把环断开，f[i][j][0]记录i到j的最小值，f[i][j][1]记录最大值，然后递推计算。记录最小值是因为两个负数乘起来可能得到一个大的正数。
  
    阅读全文
  posted @ 2007-10-05 16:47 Felicia 阅读(601) | 评论 (0)  编辑
• [动态规划]pku1189      摘要: 概率+DP，比较经典的题。按照递推的方式计算概率。
  
    阅读全文
  posted @ 2007-10-04 20:47 Felicia 阅读(784) | 评论 (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 阅读(1039) | 评论 (0)  编辑
• [动态规划]pku1163      摘要: 今天郁闷了，贴个小代码
  
    阅读全文
  posted @ 2007-09-29 22:43 Felicia 阅读(535) | 评论 (0)  编辑
• [动态规划]动态规划总结 by Amber      摘要: 动态规划总结 by Amber
  
    阅读全文
  posted @ 2007-09-29 20:25 Felicia 阅读(3939) | 评论 (0)  编辑
• [动态规划]pku3133      摘要: 强烈推荐此题！
  状态压缩DP的好题！
  分析见内
  
    阅读全文
  posted @ 2007-09-24 21:12 Felicia 阅读(1138) | 评论 (4)  编辑
• [动态规划]pku1038      摘要: 经典的状态压缩DP，《算法艺术与信息学竞赛》的例题。f[i][j]表示前i行，最后两行状态为二进制数j，嵌入的最多芯片数。第i行到第i+1行用DFS进行状态转移。
  由于第i+1行只和第i行有关，故可以用滚动数组优化。
  
    阅读全文
  posted @ 2007-09-12 20:44 Felicia 阅读(1523) | 评论 (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 阅读(791) | 评论 (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 阅读(667) | 评论 (0)  编辑
• [动态规划]pku1160      摘要: 先预处理，把第i个村子到第j个村子中，建一个邮局的最小代价算出来，存在min_cost[i][j]里。
  接下来就可以DP。设f[i][j]为前i个邮局，建在前j个村子的最小代价。那么f[i][j]可以转移到f[i + 1][j + k]，(1 <= k 且 j + k <= n)，代价是min_cost[j + 1][j + k]。
  
    阅读全文
  posted @ 2007-09-03 22:44 Felicia 阅读(1492) | 评论 (3)  编辑
• [动态规划]pku1088      摘要: 简单的记忆化搜索。很早以前做的，代码风格很乱。将就一下啦。
  
    阅读全文
  posted @ 2007-09-02 20:02 Felicia 阅读(912) | 评论 (5)  编辑
• [动态规划]pku1737      摘要: 楼爷的题。递推。f[n]表示n个结点的连通图个数，则有递推公式：
  
  void calc(int n)
  {
  f[n] = 0;
  for (int i = 1; i < n; i++)
  f[n] += f[i] * f[n - i] * (pow(i) - 1) * C(n - 2, i - 1);
  //pow(x) == 2^x
  }
  
  因为数据较多，所以预先算出f[1] -- f[50]，再输出。要用高精度。我用了标程。
  
    阅读全文
  posted @ 2007-09-02 13:53 Felicia 阅读(755) | 评论 (6)  编辑
• [动态规划]pku1946      摘要: 首先明确一点：最优解必为奶牛1..n-1轮流领跑，奶牛n撞线。且跑了x圈后，未领跑过的奶牛都耗费了x的体力。
  设f[i][j][k]表示前i-1头奶牛已领跑，现在由第i头奶牛领跑，一共跑了j圈，奶牛i耗费了k的体力。
  则f[i][j][k]可以转移到f[i][j + p][k + p^2]（耗费1分钟，奶牛i以p圈/分钟的速度继续领跑），也可转移到f[i + 1][j][j]（换成奶牛i + 1领跑，不耗费时间）。
  时间复杂度为O(nde^2.5)。
  
    阅读全文
  posted @ 2007-09-01 11:42 Felicia 阅读(477) | 评论 (1)  编辑
• [动态规划]pku1947      摘要: 推荐此题。基础树型DP。
  f[x][i](1 <= i <= p)表示以x为根的子树，变成剩下i个点的子树，且剩余子树包含根结点，需要去掉的最少边数。
  那么父结点的f值可以由它所有的儿子的f值做背包得到。
  最后的答案是min(min(f[i][p]) + 1 (2 <= i <= n), f[1][p])
  
    阅读全文
  posted @ 2007-08-31 18:27 Felicia 阅读(853) | 评论 (0)  编辑
• [动态规划]pku1848      摘要: 强烈推荐此题。树型DP。
  分析较长且带有图示，请阅读全文。
  
    阅读全文
  posted @ 2007-08-30 21:47 Felicia 阅读(1026) | 评论 (4)  编辑
• [动态规划]pku1112      摘要: 强烈推荐此题。图论和DP结合。
  分析较长，请阅读全文。
  
    阅读全文
  posted @ 2007-08-29 17:15 Felicia 阅读(904) | 评论 (4)  编辑
• [动态规划]pku2411      摘要: 经典的状态压缩DP。f[i][j]表示第i行，方格排布为二进制数j（第k位上为1表示凸出一个格子，为0表示不凸出）的方案数。用DFS进行状态转移。
  如果行数比较多的话，可以用矩阵乘法优化。因为每行的状态转移都是相同的。设烈数为m，行数为n，可以做到O(2^(3m)logn)。
  
    阅读全文
  posted @ 2007-08-28 21:03 Felicia 阅读(1407) | 评论 (12)  编辑
• [动态规划]pku2288      摘要: 经典的TSP问题变种。状态为f[i][j][k]，表示经过二进制数i所指的哈密顿路（第bi位为1表示经过该点，为0表示不经过该点），倒数第二个点为j，最后一个点为k。.value表示最大权值，.num表示能走出最大权值的路径数。若图中k到p有边，f[i][j][k]则转移到f[i'][k][p]。i' == i | (1 << p)。
  
    阅读全文
  posted @ 2007-08-28 20:47 Felicia 阅读(812) | 评论 (2)  编辑
• [动态规划]pku1141      摘要: int f[i][j]表示第i个字符到第j个字符需要添加的最少括号数。string ans[i][j] 表示第i个字符到第j个字符按照最优方案添加括号后的串。状态转移：1.f[i][j]由f[i + 1][j - 1]转移来（通过两端添括号() / [] ）。2.f[i][j]由f[i][k] + f[k + 1][j]转移来（通过串合并）。答案是ans[0][len - 1]。
  
    阅读全文
  posted @ 2007-08-27 15:55 Felicia 阅读(1211) | 评论 (3)  编辑
• [动态规划]pku1050      摘要: 枚举矩形的上边和下边，花费O(n^2)，把问题转化成一维的最大M子段和，做一个O(n)的DP。
    阅读全文
  posted @ 2007-08-26 13:51 Felicia 阅读(999) | 评论 (6)  编辑
• [动态规划]pku 部分动态规划题目列表      摘要: pku 部分动态规划题目列表
  
    阅读全文
  posted @ 2007-08-26 11:52 Felicia 阅读(6563) | 评论 (5)  编辑
• [动态规划]pku3345      摘要: 建立一个虚点（权为无穷大），从它到每个入度为 0 的点都连一条边，然后做树型DP。
  先递归算出子结点的 f 值，然后用背包的方法计算父结点的 f 值。
  
    阅读全文
  posted @ 2007-08-15 18:42 Felicia 阅读(615) | 评论 (0)  编辑