公司建设网站价格表,wordpress手机接口,沈阳正规男科医院,凡科轻站【概述】 线性动态规划#xff0c;是较常见的一类动态规划问题#xff0c;其是在线性结构上进行状态转移#xff0c;这类问题不像背包问题、区间DP等有固定的模板。 线性动态规划的目标函数为特定变量的线性函数#xff0c;约束是这些变量的线性不等式或等式#xff0c;目…【概述】 线性动态规划是较常见的一类动态规划问题其是在线性结构上进行状态转移这类问题不像背包问题、区间DP等有固定的模板。 线性动态规划的目标函数为特定变量的线性函数约束是这些变量的线性不等式或等式目的是求目标函数的最大值或最小值。 因此除了少量问题如LIS、LCS、LCIS等有固定的模板外大部分都要根据实际问题来推导得出答案。
【例题】最长公共子序列(LCS)
lanqiao0J题号1054
lanqiao0J题号1189 LCS 问题Longest Common Subsequence给定一个长度为n数组A和一个长度为m的数组B,求序列的最长公共子序列。 题目描述 输入描述 第一行为第一个字符序列都是大写字母组成以 . 结束长度小于 5000。 第二行为第二个字符序列都是大写字母组成以 . 结束长度小于 5000。 输出描述 第一行输出上述两个最长公共子序列的长度。 第二行输出所有可能出现的最长公共子序列个数答案可能很大只要将答案对求余即可。 输入输出样例 输入 ABCBDAB.
BACBBD.输出 4
7 题目大意 一个给定序列的子序列是在该序列中不一定连续删去若干元素后得到的序列。例如:X {ABCB, DA B}它的子序列有{A B,CB,A}、{AB,D}、{B, CDB}等。给定两个序列X和Y当另一序列Z既是X的子序列又是Y的子序列时称Z是序列X和Y的公共子序列最长公共子序列是长度最长的子序列。求两个最长公共子序列的长度和所有可能出现的最长公共子序列个数。
法一暴力法
先找出A的所有子序列然后 一 一 验证是否为Y的子序列。 如果A有m个元素那么A有个子序列集合的子集的个数B有n个元素总复杂度大于
法二动态规划
dp[i][j]序列Ai ()和Bj (b1~bj)的最长公共子序列的长度dp[n][m] 分解为2种情况: (1)当当前两个子序列的最后一个相同时已求得和的最长公共子序列在其尾部加上或即可得到的最长公共子序列。状态转移方程: dp[i]j] dp[i-1][j-1]1 (2当时求解两个子问题的最长公共子序列的最长公共子序列。取最大值状态转移方程: dp[i][j]max{dp[i][j-1], dp[i-1][j]}
复杂度O(nm) 代码
使用交替滚动数组 (1当时状态转移方程dp[i][i] dp[i-1][j-1]1 (2当时状态转移方程 dp[i][j] max{dp[i][j-1], dp[i-1][j]}
n, m map(int, input().split())
a [0] list(map(int, input().split())) # 从a[1]~a[n]
b [0] list(map(int, input().split())) # 从b[1]~b[n]
dp [[0] * (m 1) for _ in range(2)] # 注意这里是m不是n
now 0; old 1
for i in range(1, n 1):now, old old, nowfor j in range(1, m 1):if a[i] b[j]:dp[now][j] dp[old][j - 1] 1 else # ai≠bjdp[now][j] max(dp[now][j - 1], dp[old][j]) print(dp[now][m]) 【例题】 最长递增子序列LIS
蓝桥骑士lanqi ao0J题号1188 题目描述 小明是蓝桥王国的骑士他喜欢不断突破自我。这天蓝桥国王给他安排了 N 个对手他们的战力值分别为 a1,a2,...,an且按顺序阻挡在小明的前方。对于这些对手小明可以选择挑战也可以选择避战。身为高傲的骑士小明从不走回头路且只愿意挑战战力值越来越高的对手。请你算算小明最多会挑战多少名对手。 输入描述 输入第一行包含一个整数 N表示对手的个数。 第二行包含 N 个整数 a1,a2,...,an分别表示对手的战力值。 。 输出描述 输出一行整数表示答案。 输入输出样例 输入 6
1 4 2 2 5 6输出 4 思路
LIS给定一个长度为n的数组找出一个最长的单调递增子序列。 例:序列A{5,6,7,4,2,8,3}它最长的单调递增子序列为{5,6,7,8}长度为4。
做法
定义状态dp[i]表示以第i个数为结尾的最长递增子序列的长度。 状态转移方程:
最长的单调递增子序列max {dp[i]}复杂度 j在0~i之间滑动复杂度O(n); i的变动范围也是O(n)的;总复杂度。
动态规划:复杂度 本题DP代码提交到0J会超时。 DP不是LIS问题的最优解法有复杂度0(nlogn)的非DP解法二分查找
本题题解蓝桥杯刷题026——蓝桥骑士二分法
【例题】字符串转换
lanqiao0J题号1507 题目描述 小蓝拥有两个字符串 S,T。他希望通过如下操作使得字符 S 转换为字符串 T。 操作有一下三种 删除一个字符。插入一个字符。将一个字符改为另一个字符。问最少需要操作多少次才可以使得字符串 S 转换为字符串 T。 输入描述 输入第一行包含一个字符串 S。 输入第二行包含一个字符串 T。 1≤∣S∣,∣T∣≤2×10^3保证 S、T 只包含小写字母。 输出描述 输出一个整数表示答案。 输入输出样例 输入 abc
aa输出 2 数据范围在1≤∣S∣,∣T∣≤ 可以是的复杂度
思路 编辑距离
把长度m的A存储在数组a[1]~ a[m]长度为n的B存储在b[1]~ b[n]不用a[0]和b[0]。
定义状态dp dp[i][j]表示A的前i个字符转换B的前j个字符所需要的操作次数操作次数最少dp[m][n] 下图是AabcfBbcfe”的状态转移矩阵。 状态转移方程: (1) 若a[i] b[j]则dp[i][j] dp[i-1][j-1]。例如图中dp[2][1]处的箭头 (2) 其他情况: dp[i][j] min{dp[i-l][j-1]dp[i-1][j],dp[i][j-1]} 1。例如图中dp[4][2]处的箭头。dp[i][j]是它左、左上、上的三个值中的最小值加1分别对应以下操作:
dp[i-1][j]1删除将A的最后字符删除:dp[i][j-1]1插入在B的最后插入A的最后字符:dp[i-1][j-1]1替换将B的最后一个字符替换为A的最后一个字符。
复杂度:O(mn)
代码
(1) a[i] b[j]则dp[i][j] dp[i-1][j-1] (2其他情况: dp[i][j] min idp[i-1][j-1], dp[i-1][j], dp[i][j-1]} 1
a input() ; a a #a[0]不用用a[1]~a[m]
b input() ; b b
m len(a)-1
n len(b)-1
dp [[0]*(n 1) for _ in range(m 1)]
for i in range(1, m1 ): dp[i][0] i # 初始化
for j in range(1, n1 ): dp[0][j] j # 初始化
for i in range(1,m1):for j in range(1, n1):if a[i]b[j]: dp[i][j] dp[i-1][j-1]else:dp[i][j]min(min(dp[i-1][j], dp[i][j-1]) , dp[i-1][j-1])1
print(dp[m][n])【例题】 过河卒 题目描述 如图A 点有一个过河卒需要走到目标 B 点。卒行走规则可以向下、或者向右。同时在棋盘上的 C 点有一个对方的马该马所在的点和所有跳跃一步可达的点称为对方马的控制点。 例如上图 C 点上的马可以控制 9 个点图中的P1P2⋯P8 和 C。卒不能通过对方马的控制点。棋盘用坐标表示A 点0000、B 点n,m(1≤n,m ≤ 20)同样马的位置坐标是需要给出的。0≤马的坐标≤20。 现在要求你计算出卒从 A 点能够到达 B 点的路径的条数假设马的位置是固定不动的并不是卒走一步马走一步。。 输入描述 一行四个正整数分别表示 B 点坐标和马的坐标。 输出描述 一个整数表示所有的路径条数。 输入输出样例 输入 6 6 3 3输出 6 思路1模拟
统计路径条数看起来是个搜索题可以用DFS求解。把马的控制点标记为不能走绕过它们。不过用DFS搜索的路径数量是天文数字肯定超时。
思路2网格上的DP
在小学上过奥数的都知道这题应该用“标数法”就是在每个坐标点上记录能走的路径条数。标数法实际上就是DP的递推。
由于卒只能向下、或者向右移动所以每个点i, j的路径条数等于能走到(i-1, j)的路径条数能走到上边i, j-1的路径条数
标数法定义状态dp[ ][ ]: dp[i][j]表示卒走到坐标(i,j)时能走的路径条数。 如果不考虑马的控制点有:dp[i]b] dp[i - 1][j] dp[i][j - 1]; 也就是(i, j)点的路径条数等于它上面和左边的路径条数之和。这就是小学奥数的“标数法”的原理。 本题的限制条件是马的控制点只要令控制点的dp[i][j]0意思是卒走到该点时能走的路径条数为0即可即这个点上无路径。 代码
小技巧把坐标加2防止马的控制点越界(坐标为负)
dp [[0]*25 for i in range(25)]
s [[0]*25 for i in range(25)]
bx,by,mx,my map(int,input ().split())
bx 2; by 2; mx 2; my 2 # 把坐标加2
dp[2][1] 1 # 初始化起始点的上面一点为1 起始点为2,2
s[mx][my] 1; # 将马的9个控制点设置为1
s[mx-2][my-1]1; s[mx-2][my1]1; s[mx2][my-1]1; s[mx2][my1]1;
s[mx-1][my2]1; s[mx-1][my-2]1; s[mx1][my2]1; s[mx1][my-2]1;
for i in range(2,bx1): # 从2,2开始for j in range(2,by1):if s[i][j]1: dp[i][j]0 # 如果是马的控制点则该点不能走else: dp[i][j] dp[i - 1][j] dp[i][j - 1]
print(dp[bx][by]) # 到达终点B的路径条数
【例题】 排队列
2019年国赛题 题目描述 在一个排列中一个折点是指排列中的一个元素它同时小于两边的元素或者同时大于两边的元素。 对于一个 1 ∼ n 的排列如果可以将这个排列中包含 t 个折点则它称为一个 t1 单调序列。 例如排列 (1,4,2,3) 是一个 3 单调序列其中 4 和 2 都是折点。 给定 n 和 k请问 1 ∼ n 的所有排列中有多少个 k 单调队列 输入描述 输入一行包含两个整数 n,k (1≤k≤n≤500)。 输出描述 输出一个整数表示答案。答案可能很大你可需要输出满足条件的排列数量除以 123456 的余数即可。 输入输出样例 输入 4 2输出 12 数据范围在1000左右可以用复杂度为O(n^2)的算法。
方法一暴力法
20%的测试1kn10 暴力法:对所有排列进行检查判断是否为k单调队列。
from itertools import *
n,k map(int,input().split())
nums [i for i in range(1, n1)] # 1~n
cnt 0
for num in permutations (nums): # 检查每个排列tmp 0for i in range(n-2): # 0 ~ n-3if num[i1]num[i2] and num[i1]num[i]: tmp1 # 凸折点elif num[i1]num[i2] and num[i1]num[i]: tmp1 # 凹折点if tmp k-1 : cnt1
print(cnt %123456) 方法二DP
定义dp[ ][ ]: dp[i][i]表示序列包含1 ~i且排列为j单调队列的方案数也就是含有j-1个折点的方案数。1 ∼ n 的所有排列中 k 单调队列的个数dp[n][k]
状态转移方程: 从dp[i-1][]递推到dp[i][]把i插入到1 ~i-1的一个排列中折点数量的变化: dp[i][i] dp [ i-1 ][ j ]*jdp [ i-1 ][ j-1]*2dp [ i-1 ][ j-2 ]*(i-j)
代码
N 520
dp [[0]*N for i in range(N)]
n,k map(int,input ().split() )
dp[1][1] 1
dp[2][1] 2
for i in range(3, n1):ki min(k, i)for j in range (1,ki1):dp[i][j] dp[i-1][j]*j dp[i-1][j-1]*2if j 1: dp[i][j] dp[i-1][j-2]*(i-j)
print(dp[n][k] % 123456)【例题】砝码称重
2021年省赛题目 问题描述 你有一架天平和 N 个砝码这 N 个砝码重量依次是 。 请你计算一共可以称出多少种不同的重量 注意砝码可以放在天平两边。 输入格式 输入的第一行包含一个整数 N。 第二行包含 N 个整数。 输出格式 输出一个整数代表答案。 对于所有评测用例1≤N≤100,N个砝码总重不超过 100000。 样例输入 3
1 4 6样例输出 10样例说明 能称出的 10 种重量是1、2、3、4、5、6、7、9、10、11。 11 26−4(天平一边放 6另一边放 4) 34−1 44 56−1 66 716 946−1 1046 11146。 方法一模拟
这一题也可以直接模拟并且用set判重。
n int (input ())
w list (map(int,input ().split() ))
ans set() # 用set判重用来存用多少种答案的
ans.add(w[0])
for i in w[1:]:for j in ans.copy (): # ans.copy ()浅复制不会因为该次循环而改变ansans.add(i) # 只放新砝码i的质量ans.add(j i) # 将i和答案中每一个数放在同一侧相加if j - i ! 0: ans.add (abs(j - i)) # 将i和答案中每一个数放在不同测相减
print (len(ans))注意对集合进行初始化时不能直接ans set(5)因为创建set()函数需要的是一个可迭代对象如列表、元组、字符串等而不能直接接受一个整型变量。所以集合初始化有两种方法①创建空集合②创建集合赋予的参数必须是可迭代对象。如果我们需要在集合里添加一个元素我们应该先创建空集合ans set()然后再ans.add(5)
set()是O(logn)两层循环是O(n*ans)所以总复杂度是O(n*ans*logn)
方法二DP
建模给定n个正整数从中选出若个数字组合每个数字可以加或者减最终能得到多少种正整数结果。 DP状态定义: dp(i,j)表示前i个数字选择若干个加或者减能否获得和为j。
DP状态转移方程: dp(i, j) dp(i-1,j) l dp(i-1,j- wi) l dp(i-1, jwi) 状态转移方程中有三种情况 dp(i-1,j)不用第i个数字和为j dp(i-1, j -w)用第i个数字且做减法等价于用i-1个数字实现 j -Wi
dp(i-1,jw;)用第i个数字且做加法等价于用i-1个数字实现 jwi
代码
n int(input())
W list(map(int, input().split()))
s sum(W) # 所有砝码之和
dp [[0] * (s 1) for _ in range(n)]
for i, w in enumerate(W): # 初始化前i个的砝码的质量为wdp[i][w] 1
for i in range(1, n): # 第0行不需要管因为只有一个质量for j in range(1, s1):if dp[i - 1][j]: # 找到前i-1个可以组合出质量jdp[i][j] 1 # 不选第i个前i个也可以组合出质量jdp[i][j W[i]] 1 # 用第i个数字且做加法if j ! W[i] :dp[i][abs(j - W[i])] 1 # 用第i个数字且做减法
print(sum(dp[-1])) # dp[-1]就是dp的第一维的最后一个即最后一行
通过90%测试。
对方法一模拟进行优化
n int (input ())
w list (map(int,input ().split() ))
w.sort() # 从小到大排序可以减少计算时间
ans set() # 用set判重用来存用多少种答案的
ans.add(w[0])
for i in w[1:]:for j in ans.copy (): # ans.copy ()浅复制不会因为该次循环而改变ansans.add(i) # 只放新砝码i的质量ans.add(j i) # 将i和答案中每一个数放在同一侧相加ans.add (abs(j - i)) # 将i和答案中每一个数放在不同测相减
# 判断是否质量为0放在两层for循环之外减少时间复杂度
if 0 in ans: # 质量为0的不考虑ans.remove(0)
print (len(ans))对方法二DP进行优化
n int(input())
W list(map(int, input().split()))
W.sort() # 从小到大减少时间复杂度
s sum(W) # 所有砝码之和最大值
si [sum(W[0:i]) for i in range(1,n1)] # 质量W的前缀和
dp [[0] * (s 1) for _ in range(n)]
for i, w in enumerate(W): # 初始化前i个的砝码的质量为wdp[i][w] 1
for i in range(1, n): # 第0行不需要管因为只有一个质量for j in range(1, si[i]1):if dp[i - 1][j]: # 找到前i-1个可以组合出质量jdp[i][j] 1 # 不选第i个前i个也可以组合出质量jdp[i][j W[i]] 1 # 用第i个数字且做加法dp[i][abs(j - W[i])] 1 # 用第i个数字且做减法
print(sum(dp[-1][1:])) # dp[-1]就是dp的第一维的最后一个即最后一行[1:]:不考虑质量为0的情况
经过优化后的两段代码均通过100%测试。
【例题】数字三角形 2020年省赛 题目描述 上图给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径把路径上面的数加起来可以得到一个和你的任务就是找到最大的和。 路径上的每一步只能从一个数走到下一层和它最近的左边的那个数或者右 边的那个数。此外向左下走的次数与向右下走的次数相差不能超过 1。 输入描述 输入的第一行包含一个整数 N (1≤N≤100)表示三角形的行数。 下面的 N 行给出数字三角形。数字三角形上的数都是 0 至 100 之间的整数。 输出描述 输出一个整数表示答案。 输入输出样例 输入 5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5输出 27 思路
本题要求向左走的次数与向右走的次数差值不超过1当到达最后一层时一定是落在中间位置。
如果层数是奇数最后一层落在正中间元素上如果层数是偶数最后一层落在第N/2或第N/21个元素上。
定义状态dp[ ][ ]dp[i]i]表示从顶部到第i层横向第j个数最大路径和。它只能从上一层的左边或右边转移而来。
代码
n int(input())
a [list (map(int, input ().split())) for i in range (n)] # 用来读取每行个数不同的元素
#数组a[][]同时当成dp[][]用
for i in range(1, n):for j in range (0, i 1):if j 0: a[i][j] a[i-1][j] # 最左边元素elif j i: a[i][j] a[i-1][j-1] # 最右边元素else:a[i][j] max(a[i-1][j-1 : j1]) # 中间从上面左边/从上面右边
if n 1: print(a[-1][n//2]) # 奇数行在正中间
else: print (max(a[-1][n//2-1], a[-1][n//2])) # 偶数行在正中间左边或者右边
