-含章可贞-

分类

题解(7)

/ 注册

全部文章（共5篇）

题解 | #信封嵌套#

补一个python3答案：方法：按宽递增排序后，求长的最长严格上升子序列，同时要求宽不相等注意：为保证宽不相等，可以使等宽区域内按长逆序排列，这样严格上升子序列在每组宽中只能取一个长，例：输入排序前： [[3, 4], [2, 3], [4, 5], [1, 3], [2, 2], [3...

Python3 动态规划

2022-05-17

1 301

题解 | #合唱队形#

考虑分别以各个位置为中心折点，在每个位置求其：之前的最长严格上升子序列长度（要求包括自己）：实际就是题目DP14中dp数组之后的最长严格下降子序列长度（要求包括自己）：可通过两次数组反转得到然后就是简单的加减法，得到以各个位置为中心折点时，最少要Out的人数，取最小 def maxIncS...

Python3 动态规划

2022-05-17

2 235

题解 | #拦截导弹#

Q1：很明确就是最长递减子序列的长度 Q2：根据Dilworth定理:最少的下降序列个数就等于整个序列最长上升子序列的长度 n=eval(input()) heights=list(map(int,input().split())) dp=[1]*n # Q1:最长递减子序列 dp2=[1]*n #...

Python3 动态规划

2022-05-16

6 299

题解 | #[NOIP2002 普及组] 过河卒#

n,m,x,y=map(int,input().split()) assert(1<=n<=20) assert(1<=m<=20) assert(0<=x<=20) assert(0<=y<=20) board=[[1 for _ in range(...

Python3 动态规划

2022-05-16

1 256

题解 | #环形数组的连续子数组最大和#

将环转换为普通数组思考：当目标是越过了末尾的环中子串,找到普通数组中和为负的最小子串，用和减去找普通和最大的子串两者比较取更大特殊情况: 全负or全0：输出最大数全正，直接取和 n=eval(input()) a=list(map(int,input().split())) dp1...

Python3 动态规划

2022-05-15

4 360