-
导弹拦截
普通的求一个最长上升子序列，一个最大下降子序列，输出就OK了，是n^2的复杂度而这样就过不了300000的点了所以我们就用二分查找的办法来优化，因为输入的复杂度无法优化，所以复杂度是nlogn最长上升子序列上升思路：有一个low数组，low[i]是长度为i的最长子序列的最小值维护一个上升序列，如果加入的数>low[len],最长子序列就可以更新了，如果小于等于，则把正好大于他的一个数改为他。 …
-
方格取数or传纸条
用简单的搜索，之前听了从清北写的，一直没写博客，现在补上这两个题实际上是一样的，传纸条虽然有一个是倒着传，其实和正着传是一样的，所以是一样的就是用一个四维数组，记下两个点的坐标，两个点都可以向上或向下走，所以可以转移到四种情况，就是我下面分的四种还可以用动归动态转移方程是dp[x][y][x2][y2]=max(dp[x][y-1][x2][y2-1],dp[x-1][y][x2][y2-1],d …
-
计算系数
水题一个，不过哪位大神能告诉我为什么，拆开系数符合组合数公式12345678910111213141516171819202122232425262728293031#include<cstdio>#include<iostream> using namespace std;#define p 10007int m,n;int c[55][55];int dp[55][55 …
-
最大正方形
dp处理一个矩阵前缀和，就可以O(n)的求出矩阵的和了，而且只有和为完全平方数才是正方形，因为数据只有1吗，要是不是一的话就不容易了这样再枚举一个起点，和一个边长就是任意一个正方形了，再优化剪枝一下，就可以0ms过了1234567891011121314151617181920212223242526272829303132#include<cstdio>#include<ios …
-
编辑距离
动态转移方程按三个步骤来，就是从f[i-1][j-1],f[i-1][j],f[i][j-1]+1转移过来所以就是f[i][j]=min(f[i-1][j-1],f[i-1][j],f[i][j-1])+1123456789101112131415161718192021222324252627282930#include<cstdio>#include<cstring> …
-
统计单词个数
这个题和之前一个乘法最大思路差不多，就是如果要划分k份之前已经划分了k-1份，划分为k份的就是由，k-1推来的再加上第k份的单词个数，所以就枚举前面k-1分到的位置，是k~当前位置，取最大值，就是结果了然后单词个数就在线统计就行了，因为以一个数为首字母的只能用一次，所以找最短的单词记下来就行了。1234567891011121314151617181920212223242526272829303 …