FLOWS

分类

DP(1) 扫描线(1) 未归档(13)

/ 注册

全部文章（共15篇）

Game on Tree(期望线性性)

Game on Tree 题意：有一颗树，每一步选择一个节点，则这个节点以及它的子树上所有节点都会被染色，问染色完整棵树需要的步数的期望值分析：由于以前没怎么做过求期望的题，我看到这题的第一想法是找出所有的染色方法，计算他们的步数的平均值，但是这样想想就很复杂… 所以正确的解法利用期...

2019-07-19

0 760

POJ1679 The Unique MST（次小生成树(kruskal版)）

POJ1679 The Unique MST 题意：判断在有n个点，m条边的无向图中最小生成树是否唯一分析：我想你一定会最小生成树了不会的话先去学一波最小生成树再回来吧传送门例如下图：我们很容易找到它的一颗最小生成树，如下图：我们要找次小生成树，一定是每次把不在最小生成...

2019-07-17

0 576

POJ2449 Remmarguts' Date(k短路(A*优化))

POJ2449 Remmarguts’ Date 题意：有n个节点，m条边，求任意两点间的第k短路径长度分析：对Astar算法不熟可以移步大佬博客：https://blog.csdn.net/hitwhylz/article/details/23089415 讲得很详细，但比较长我下...

2019-07-17

0 862

HDUOJ1264 Counting Squares(扫描线解法)

HDUOJ1264 Counting Squares 题意：很裸很裸的求面积并问题分析：也没啥好分析的，就是个板子题但是这题有个坑点，输入的对角坐标并不一定是按左下、右上的顺序，需要自行判断我因为这个WA了5发… 代码： #include <bits/stdc++.h&g...

扫描线线段树

2019-07-16

0 533

HDUOJ1024 Max Sum Plus Plus(详解)

HDUOJ1024 Max Sum Plus Plus 题意：给一个包含n个数的数组,从中选出m个没有交集的区间，使这m个区间的区间和的和最大，求出这个最大值分析: 其实这个题n的范围如果不是那么大，能用二维dp写的话并不算难但是n就是1e6那么大，即使m的范围比较小基本也只能写一维d...

2019-07-16

0 616

洛谷P1052 过河

洛谷P1052 过河题意：题意很明了，就不赘述了（其实是我语文水平有限还很懒… ）分析: dp很好想，状态转移方程也简单： d p ...

2019-07-15

0 561

洛谷P1044 栈

洛谷P1044 栈题意：很简单，自己看吧… 分析: 这种题刚上手很容易当作一个找规律题来做如果你对卡特兰数比较敏感，当你列完前3项可能就能秒了这题如果你不知道卡特兰数，那好吧，当我上面没说下面开始正经地分析：设dp[i]表示序列长度为i时经过操作可能得到的输出序列的总数在一个长...

2019-07-15

0 685

洛谷P1040 加分二叉树

洛谷P1040 加分二叉树题意：按中序遍历的顺序给出一棵二叉树各个节点的值，求出这棵树的最大得分，以及此时的前序遍历记分规则如下：有两个子树：两个子树分数的乘积加上根的值有一个子树：该子树的分数加上根的值没有子树(叶子节点)：该节点的值分析：输入数据是二叉...

2019-07-15

0 563

洛谷P2015 二叉苹果树

洛谷P2015 二叉苹果树题意：给一棵二叉树，每条边有一个权值，去掉某些边之后，使剩下的二叉树边的权值之和最大分析：这是一个典型的树状DP题状态转移方程： d p ...

2019-07-14

0 522

洛谷P1026 统计单词个数

洛谷P1026 统计单词个数题意：给一个字符串（题目中是以20个字符为一组输入的），字符串被分为k段，然后给定几个“单词”，问各段包含的单词总数最多是多少？（emmm，我jio得我应该说清楚了，看不明白的话还是点击上方链接看原题吧…）分析：需要进行字符串匹配，所以很容易想到哈希此处...

DP Hash

2019-07-14

0 574