静寂旮旯

分类

题解(43)

/ 注册

全部文章（共46篇）

题解 | #不相邻取数#

解题思路：此题必须空间优化，一般情况：dp[i]=max(dp[i−2]+v[i],dp[i−1])dp[i] = max(dp[i-2]+v[i],dp[i-1])dp[i]=max(dp[i−2]+v[i],dp[i−1]) #include<bits/stdc++.h> us...

C++ 动态规划

2022-04-28

0 296

题解 | #最长回文子序列#

解题思路：建立模型为最长公共子序列。则只要求出s和sr（倒序）的最长公共子序列即可。一般情况：dp[i][j]=max(dp[i−1][j−1]+(int)(s[i]==sr[j]),max(dp[i−1][j],dp[i][j−1]))dp[i][j] = max(dp[i-1][j-1]+...

C++ 动态规划

2022-04-28

0 320

题解 | #正则表达式匹配#

解题思路：题是写出来了，但是感觉像假做。可能是测试数据不行。有时写递归感觉心里没底。先递归解决问题，再记忆化，就成了dp，估计后面还有优化的空间。有时候写dp，先费劲脑力把递归思路想出来。管它什么套路。首先考虑一般情况。想要使得str和pattern匹配，从结尾开始，考虑我从哪里来。这里要分一...

C++ 动态规划字符串

2022-04-27

2 330

题解 | #计算字符串的编辑距离#

解题思路：知道用dp，那么dp[i][j]表示在动态规划过程中表示字符串s1走到i位置，以及字符串s2走到j位置，所需要的最短字符串距离（需要修改的最小次数）一般情况下，dp[i][j]应该是通过三种操作（插入一个字符，删除一个字符，以及修改一个字符）得到的最小操作次数，先要判断一下s1[i]...

C++ 动态规划

2022-04-26

0 206

题解 | #最长公共子序列(一)#

解题思路：利用dp[i][j]表示以s1以i为结尾的子串，s2以j为结尾的子串中有最长的公共子序列的长度，那么普遍情况i != 0 and j != 0i\ !=\ 0\ and\ j\ !=\ 0i != 0&nb...

C++ 动态规划

2022-04-26

0 277

题解 | #滑雪#

解题思路：关键点，是找到起始的位置，在输入地图的同时，把点(i,j)的高度和其坐标保存下来pointshight(i,j)points_{hight(i,j)}pointshight(i,j),再将points按照hight排序。那么拍完序以后的内容就是我们要处理点的顺序。接下来只要对于po...

C++ 动态规划

2022-04-24

1 355

题解 | #信封嵌套#

解题思路：对等于求解最长上升子序列，先将输入按照升序排列。然后求解。对于当前信封i有：在此之前多所有嵌套0<=j<i0<=j<i0<=j<i只要满足v[i].first > v[j].first && v[i].second >...

C++ 动态规划

2022-04-24

0 368

题解 | #龙与地下城游戏问题#

解题思路：入坑思路：起点和终点搞反，即把坐标（n-1，m-1）作为最终解出口。发现问题在求解的过程中总是要回溯到从（0，0）点到当前位置所经过路径上的血瓶计算，感觉问题始终在搞清和没搞清之间，非常痛苦。正确思路：是从（n-1，m-1）点到（0，0）点的求解，在一路走的过程当中只需要考虑当前存...

C++ 动态规划

2022-04-24

3 455

题解 | #合唱队形#

解题思路：队形的特征是从T1<...<Ti>...>TkT_1 <...< T_i >...>T_kT1<...<Ti>...>Tk,(1<=i<=k)(1 <= i <= k)(1<=i...

C++ 动态规划

2022-04-15

0 244

题解 | #拦截导弹#

解题思路：入坑思路，求得最长不严格下降子序列以后，思路一直在记录经历过的点上，思索良久发现不可行。最后查看dp数组中的值，想发现一些规律，迷惑地发现，只要在dp数组中求出严格上升子序列的个数就可以获得答案，结果过了5个测试点后挂了。接下来没有任何思路了。通过看题解知道了一个牛逼的Dilwort...

C++ 动态规划

2022-04-15

0 386