DP-坐标规则型动态规划.ppt

坐标规则型动态规划 长沙市雅礼中学朱全民 Robots 在一个n m的棋盘内 一些格子里有垃圾要拾捡 现在有一个能捡垃圾的机器人从左上格子里出发 每次只能向右或者向下走 每次他到达一个点 就会自动把这个点内的垃圾拾掉 问 最多能拾多少垃圾 在最多的情况下 有多少种拾垃圾方案 数据范围 n 100 m 100 样例分析 最多能拾5块 有4种方法 分析 1 因为机器人只能向右或者向下走 符合无后效性原则 于是考虑动态规划 设F i j 表示从 1 1 点开始走到 i j 的时候 最多捡了多少垃圾 F i j Max f i 1 j f i j 1 c i j 其中C i j 1表示 i j 点有垃圾 C i j 0表示没有1 i n 1 j m 决策2种时间复杂度为O n m 分析 2 设G i j 表示在f i j 最大的时候 有多少种方案 捡到f i j 的垃圾只能从两个方向来走 方案数累加即可 因此 g i j g i 1 j k g i j 1 L如果f i 1 j c i j f i j 则K 1否则K 0 如果f i j 1 c i j f i j 则L 1否则L 0时间复杂度O n m 矩阵取数游戏 NOIP2007 对于一个给定的n m的矩阵 矩阵中的每个元素aij为非负整数 游戏规则如下 1 每次取数时须从每行各取走一个元素 共n个 m次后取完矩阵所有的元素 2 每次取走的各个元素只能是该元素所在行的行首或行尾 3 每次取数都有一个得分值 为每行取数的得分之和 每行取数的得分 被取走的元素值 2i 其中i表示第i次取数 从1开始编号 4 游戏结束总得分为m次取数得分之和 求出取数后的最大得分 样例 输入23123342输出82第1次 第一行取行首元素 第二行取行尾元素 本次的氛围1 21 2 21 6第2次 两行均取行首元素 本次得分为2 22 3 22 20第3次 得分为3 23 4 23 56 总得分为6 20 56 82 数据范围 60 的数据满足 1 n m 30 答案不超过1016100 的数据满足 1 n m 80 0 aij 10001 21 2 21 62 22 3 22 203 23 4 23 561 21 2 22 3 23 2 21 3 22 4 23 分析 首先 n行求值可以独立考虑 设f i j 表示区间i j的最优值f i j max f i 1 j w a i f i j 1 w a j 其中w w w 即w 2需要做若干次高精度加法和乘法 直到求出 max f i i w a i i 1 m 为止 传纸条 NOIP2008 小渊坐在矩阵的左上角 坐标 1 1 小轩坐在矩阵的右下角 坐标 m n 从小渊传到小轩的纸条只可以向下或者向右传递 从小轩传给小渊的纸条只可以向上或者向左传递 班里每个同学都可以帮他们传递 但只会帮他们一次 每个同学愿意帮忙的好感度有高有低 可以用一个0 100的自然数来表示 数越大表示越好心 小渊和小轩希望尽可能找好心程度高的同学来帮忙传纸条 即找到来回两条传递路径 使得这两条路径上同学的好心程度只和最大 现在 请你帮助小渊和小轩找到这样的两条路径 1 m n 50 贪心 很容易想到一个算法 求出1个纸条从 1 1 到 M N 的路线最大值 删除路径上的点值再求出1个纸条从 M N 到 1 1 的路线最大值 统计两次和上述算法很容易找出反例 如下图 第1次找最优值传递后 导致第2次无法传递 分析 贪心算法错误 因此我们需要同时考虑两个纸条的传递 由于小渊和小轩的路径可逆 因此 尽管出发点不同 但都可以看成同时从 1 1 出发到达 M N 点 设f i1 j1 i2 j2 表示纸条1到达 i1 j1 位置 纸条2到达 i2 j2 位置的最优值 则有 其中 i1 j1 i2 j2 1 i1 i2 M 1 j1 j2 N时间复杂度O N2M2 分析2 另一种思路 每个纸条都需要走M N步才能达到目标 因此 设F k i1 i2 表示两个纸条都走了K步 第1个纸条横坐标为i1 第2个纸条横坐标为i2的最优值 则两个纸条的纵坐标分别为j1 K i1 j2 K i2 状态转移方程如下 其中i1i21 i1 i2 M 1 k N M时间复杂度O N M M2 免费馅饼 SERKOI最新推出了一种叫做 免费馅饼 的游戏 游戏在一个舞台上进行 舞台的宽度为W格 天幕的高度为H格 游戏者占一格 开始时 游戏者站在舞台的正中央 手里拿着一个托盘 游戏开始后 从舞台天幕顶端的格子中不断出现馅饼并垂直下落 游戏者左右移动去接馅饼 游戏者每秒可以向左或右移动一格或两格 也可以站在愿地不动 馅饼有很多种 游戏者事先根据自己的口味 对各种馅饼依次打了分 同时在8 308电脑的遥控下 各种馅饼下落的速度也是不一样的 下落速度以格 秒为单位 当馅饼在某一秒末恰好到达游戏者所在的格子中 游戏者就收集到了这块馅饼 写一个程序 帮助我们的游戏者收集馅饼 使得收集的馅饼的分数之和最大 输入数据 第一行 宽度W 1 99奇数 和高度H 1 100整数 接下来给出了一块馅饼信息 由4个正整数组成 分别表示了馅饼的初始下落时刻 水平位置 下落速度 分值 游戏开始时刻为0 从1开始自左向右依次对水平方向的每格编号 输出数据 收集到的馅饼最大分数之和 由上图可知 尽管下落了4个馅饼 但只能接到3个 第1时刻可以接到分值为5的馅饼第2时刻可以接到分值为3的馅饼第3时刻可以接到分值为4的馅饼因此馅饼的总分值为5 3 4 12 分析 由于馅饼下落的时间和速度都不同 人只能向左右移动 馅饼只能向下移动 人和馅饼都同时移动 思考起来比较复杂 因此我们需要转变思路 算出每个时刻落到最底层的每个格子有多少分值的馅饼 如果将馅饼当成参照物 则馅饼向下落 可以看成馅饼不动 人往上走去摘取馅饼 这样人每1时刻都可以走到上一行的5个格子 如右图 动态规划 计算出每个格子每个时刻可能达到的馅饼分值 填入W H的天幕表 其中C i j 表示天幕的第i行第j列的馅饼分值 即第i时刻 馅饼落到最底行的馅饼分值 设F i j 表示人走到第i行j列所取得的馅饼最大分值和 则有 0 i T 1 j W 决策数为5个时间复杂度为O 5WT 三角蛋糕 一块边长为n的正三角形的大蛋糕 一些被老鼠咬坏了 如下图黑色部分 现想把该蛋糕切出一块最大的没被老鼠咬坏正三角形的蛋糕 求切出的最大的三角形面积n 100 向上的三角形 设顶点坐标为 i j 的三角形最大高度为F i j 显然 F i j MIN F i 1 j 1 F i 1 j 1 1 当C i 1 j 表示这个三角形没被老鼠咬坏 向下的三角形 设顶点坐标为 i j 的三角形最大高度为G i j 显然 G i j MIN G i 1 j 1 G i 1 j 1 1 当C i 1 j 表示这个三角形没被老鼠咬坏 分析 分别求F i j 和G i j 1 i n 1 j 2n 1因此 时间复杂度O N2 答案为高度的平方 证明如下 假设最大高度为W则三角形个数为 2W 1 W2 主程序 fori 1tondo 倒三角情况 forj ito2 n idoif c i j and imod2 jmod2 then 如果该位置没被吃 而且必须是头朝下的三角 beginifc i 1 j thenf i j 1elsef i j min f i 1 j 1 f i 1 j 1 1 是否可以从上面的位置转移过来堆成更大的三角形 iff i j ansthenans f i j end 正三角情况程序与上类似 总结 规则类动态规划有一个共性 那就是在一个矩阵中 一般是二维矩阵 当然可能有更加复杂的图形 给出一些规则 然后按规则去做某些决策 我们思考这类问题的基本方法是 以坐标为状态 坐标之间的转换关系 一般利用问题给出的规则进行决策转移 如下图 状态转移方程一般可描述如下 F i j Max f i 1 k 决策 这里k为规则数