| 动态规划 | 您所在的位置：网站首页 › 线形是什么样子 › 动态规划 |
|
【概述】
线性动态规划，是较常见的一类动态规划问题，其是在线性结构上进行状态转移，这类问题不像背包问题、区间DP等有固定的模板。 线性动态规划的目标函数为特定变量的线性函数，约束是这些变量的线性不等式或等式，目的是求目标函数的最大值或最小值。 因此，除了少量问题（如：LIS、LCS、LCIS等）有固定的模板外，大部分都要根据实际问题来推导得出答案。 【常见问题】 序列问题：点击这里字符串编辑距离：点击这里最大和问题：点击这里 【例题】 1.序列问题： Monkey and Banana（HDU-1069）(LIS)：点击这里求最长不下降序列（信息学奥赛一本通-T1259）(LIS)：点击这里最长上升子序列（信息学奥赛一本通-T1289）(LIS)：点击这里怪盗基德的滑翔翼（信息学奥赛一本通-T1286）(LIS)：点击这里登山（信息学奥赛一本通-T1283）(LIS)：点击这里拦截导弹（信息学奥赛一本通-T1260）(LIS)：点击这里拦截导弹（信息学奥赛一本通-T1289）(LIS)：点击这里导弹拦截（洛谷-P1020）(二分+LIS)：点击这里友好城市（信息学奥赛一本通-T1289）(排序+LIS)：点击这里合唱队形（洛谷-P1091）(两遍 LIS)：点击这里 同题：合唱队形（信息学奥赛一本通-T1264）：点击这里Eating Together（POJ-3670）(两遍 LIS)：点击这里Super Jumping! Jumping! Jumping!（HDU-1087）(LIS 的和)：点击这里最大上升子序列和（信息学奥赛一本通-T1285）(LIS 的和)：点击这里Common Subsequence（HDU-1159）(LCS)：点击这里最长公共子序列（信息学奥赛一本通-T1289）(LCS)：点击这里回文字符串（51Nod-1092）(LCS)：点击这里公共子序列（信息学奥赛一本通-T1297）(LCS)：点击这里最长公共子上升序列（信息学奥赛一本通-T1306）(LCIS)：点击这里 2.字符串编辑距离 编辑距离（信息学奥赛一本通-T1276）：点击这里计算字符串距离（信息学奥赛一本通-T1298）：点击这里相似基因（洛谷-P1140）(字符串距离+模拟)：点击这里 3.求和问题 序列相关 Max Sum（HDU-1003）(序列最大和)：点击这里糖果（信息学奥赛一本通-T1299）(序列最大和)：点击这里大盗阿福（信息学奥赛一本通-T1301）(子序列和)：点击这里小a的子序列（2019牛客寒假算法基础集训营 Day1-F）(子序列和)：点击这里Milking Time（POJ-3616）(贪心+序列最大和)：点击这里乘积最大（信息学奥赛一本通-T1275）(子序列最大乘积)：点击这里Maximum sum（信息学奥赛一本通-T1305）(最大子段和)：点击这里 矩阵相关 最低通行费（信息学奥赛一本通-T1287）(矩阵最小和)：点击这里Vasya And The Mushrooms（CF-1016C）(矩阵最大和)：点击这里摘花生（信息学奥赛一本通-T1284）(矩阵最大和)：点击这里命运（HDU-2571）(矩阵最大和)：点击这里最大正方形（洛谷-P1387）(最大子矩阵)：点击这里最大子矩阵（信息学奥赛一本通-T1282）(最大子矩阵)：点击这里Likecloud-吃、吃、吃（洛谷-P1508）(最大子矩阵和)：点击这里最大子矩阵（信息学奥赛一本通-T1224）(最大子矩阵和)：点击这里创意吃鱼法（洛谷-P1736）(最大子矩阵和)：点击这里方格取数（信息学奥赛一本通-T1277）(矩阵最大路径)：点击这里 数字三角形相关 数塔（HDU-2084）：点击这里数字三角形（洛谷-P1216）：点击这里 同题：三角形最佳路径问题（信息学奥赛一本通-T1288）：点击这里数字金字塔（信息学奥赛一本通-T1258）：点击这里免费馅饼（HDU-1176）(数字三角形思想)：点击这里橱窗布置（信息学奥赛一本通-T1279）(数字三角形思想)：点击这里鸡蛋的硬度（信息学奥赛一本通-T1300）(数字三角形思想)：点击这里 4.其他 The Cow Lexicon（POJ-3267）(字符匹配+线性DP)：点击这里超级楼梯（HDU-2040）(分治+线性DP)：点击这里Problem Solving（POJ-3265）(分治+线性DP)：点击这里股票买卖（信息学奥赛一本通-T1302）(分治+线性DP)：点击这里小b和排序（51Nod-2484）(分治+线性DP)：点击这里数的划分（洛谷-P1025）(分治+线性DP)：点击这里 同题：数的划分（信息学奥赛一本通-T1304）：点击这里奇怪的电梯（洛谷-P1135）(分治+线性DP)：点击这里 同题：奇怪的电梯（信息学奥赛一本通-T1360）点击这里Race（LightOJ-1326）(打表+线性DP)：点击这里Crossing River（信息学奥赛一本通-T1232）(贪心+线性DP)：点击这里Telephone Wire（POJ-3612）(预处理+线性DP)：点击这里山区建小学（信息学奥赛一本通-T1197）(预处理+线性DP)：点击这里挖地雷（信息学奥赛一本通-T1262）(递归输出+线性DP)：点击这里机器分配（信息学奥赛一本通-T1266）(递归输出+线性DP)：点击这里尼克的任务（洛谷-P1280）(逆序+线性DP)：点击这里复制书稿（信息学奥赛一本通-T1278）(前缀和+线性DP)：点击这里判断整除（信息学奥赛一本通-T1195）(数论基础+线性DP)：点击这里Increasing Frequency（CF-1082E）(区间变换技巧+线性DP)：点击这里 |
| CopyRight 2018-2019 实验室设备网 版权所有 |