现在位置: 首页 > 算法 > 文章
2018年09月21日 算法 ⁄ 共 2219字 评论关闭
题目链接:   poj 3422 题目大意:   给出NxN的数字矩阵,左上角走到右下角(只能向右或向下走),sum记录走过点值的和                   走过的点值置为0,问走K次,求sum的最大值 解题思路:   开始想到的是K次最长路,结果WA了                   因为每次走最长路会导致下次走的时候不是最优解                   建立费用流模型,把每个顶点T,分成两个顶点T和T''                   因为要限制每个顶点的值只加一次,T->T...
阅读全文
2018年09月21日 算法 ⁄ 共 866字 评论关闭
题目链接:   poj 1088 题目大意:   给出NxM的矩阵,每个点的值都不同                   若某点四个方向中某个方向的值比它小则可以移动,求能够走的最长步数 解题思路:   经典的状态压缩Dp,Dp[ x ][ y ]记录从(x , y)点出发能走的最长步数                   Dp[ x ][ y ]=Max(Dp[ x ][ y ],DFS(xx , yy) + 1)                   若某个点之前已经走过,则不用再走,直接返回之前所能走到的最大值 代码: #include <stdi...
阅读全文