动态规划一直是ACM竞赛中的重点,也是难点(对于我这种水平),因为该算法时间效率高,代码量少,多元性强、灵活度高,主要考察思维能力、建模抽象能力。学了这么久动态规划,虽然还只是个菜菜= =,但还是想总结一下,总得给学弟学妹留下一些什么吧。                                 &…

2021年5月4日 0条评论 26点热度 阅读全文

小a与星际探索 小结: 其实我是没想到为什么我会被这个题卡住的,看来是自己动归的题少做了,不然也不会这样。只能说自己太弱了,还需要好好努力,向各位大佬靠拢一下才行。 题意: 题意是,给你n个数的序列,然后这个满足p[i]>p[j],点i才能到点j。然后问,原点为p[1],然后有飞船的维修值,请问,怎样到达点n才能使登陆点n时的价值最大。其中到达每一个点就会变成,t=a[i]^a[j]. 题解: 非常感谢@sugarbliss,及时发现问题,原来昨天的数据有点弱,之前的代码都过不了,居然还有面子给贴上来的(自愧…

2019年1月22日 0条评论 5点热度 阅读全文

https://blog.csdn.net/qq_32400847/article/details/51148917#commentsedit https://blog.csdn.net/u011815404/article/details/79703231 https://blog.csdn.net/mmc2015/article/details/73558346 很好的三篇详细讲解动态规划的博客,大家可以学学。 动态规划有的时候总是和递推公式和状态转移方程缠在一起,他们之间有着紧密的联系,DP往往都是这样的解法…

2019年1月16日 0条评论 6点热度 阅读全文

题目1 : 凸多边形 时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 给定一个凸多边形的N个顶点。你需要在凸多边形内找到M个点,使得这M个点也围成一个凸多边形,并且围成的面积尽可能大。 输入 第一行包含两个整数N和M,意义如前文所述。 接下来N行,每行两个整数Ai和Bi,表示按照逆时针顺序排列的凸多边形顶点坐标。 对于30%的数据,满足N<=5 对于100%的数据,满足N<=100 对于100%的数据,满足3<=M<N, |Ai|,|Bi|<=10000 …

2019年1月14日 0条评论 2点热度 阅读全文

You have a number of envelopes with widths and heights given as a pair of integers (w, h). One envelope can fit into another if and only if both the width and height of one envelope is greater than the width and height of the other envelope. What is the maximu…

2019年1月8日 0条评论 3点热度 阅读全文

链分治 链分治就是树链剖分。 在需要回答在子树/或结点到根路径查询时,由于 d f s dfs dfs序的连续性,可以用到树链剖分将复杂度降到 l o g 2 n log^2n log2n。 先不考虑具体如何维护每个点的 d p dp dp值,假设转移是 O ( 1 ) O(1) O(1)的,可以用线段树维护,那么修改某个点的 d p dp dp值实际上就是修改了它到根路径上的值,查询答案即为根结点上的值。 在链分治后,只会跳 l o g n logn logn次链,每次链内/链与链交接处都可以 l o g n l…

2018年11月15日 0条评论 7点热度 阅读全文

传送门:题目 题意: 给一个图,求两点权值累加和的最大值,点的权值可能为负数。 题解: 我们可以先拓扑排序一下,然后从起点到终点dp一下,记录每个点的答案,然后求答案的最大值 AC代码: #include<iostream> #include<cstring> #include<cstdio> #define debug(x) cout<<#x<<" = "<<x<<endl; #define INF 0x3f3f3f3f usin…

2018年9月8日 0条评论 10点热度 阅读全文

6902: Trie树 时间限制: 1 Sec  内存限制: 128 MB 提交: 176  解决: 37 [提交] [状态] [讨论版] [命题人:admin] 题目描述 字母(Trie)树是一个表示一个字符串集合中所有字符串的前缀的数据结构,其有如下特征: 1.树的每一条边表示字母表中的一个字母 2.树根表示一个空的前缀 3.树上所有其他的节点都表示一个非空前缀,每一个节点表示的前缀为树 根到该节点的路径上所有字母依次连接而成的字符…

2018年7月31日 0条评论 8点热度 阅读全文

题目描述 字母(Trie)树是一个表示一个字符串集合中所有字符串的前缀的数据结构,其有如下特征: 1.树的每一条边表示字母表中的一个字母 2.树根表示一个空的前缀 3.树上所有其他的节点都表示一个非空前缀,每一个节点表示的前缀为树 根到该节点的路径上所有字母依次连接而成的字符串。 4.一个节点的所有出边(节点到儿子节点的边)中不存在重复的字母。   单词“A”“to”“tea”“ted”“ten”“i”“in”“inn”对应的Trie树 现在Matej手上有N个英文小写字母组成的单词,他想知道,如果将这N…

2018年7月30日 0条评论 7点热度 阅读全文

目录   ——下面列出用动态规划如何解决此问题—— ①计算若干层楼用若干部手机最少需要摔多少次 ②计算用若干部手机摔若干次最多可以确定多少层楼 原题描述:         x星球的居民脾气不太好,但好在他们生气的时候唯一的异常举动是:摔手机。 各大厂商也就纷纷推出各种耐摔型手机。x星球的质监局规定了手机必须经过耐摔测试,并且评定出一个耐摔指数来,之后才允许上市流通。      …

2018年6月2日 0条评论 4点热度 阅读全文