Leven_

分类

2019寒假集训系列(6) 2019春季假集训系列(9) 2019暑期集训系列(12) BZOJ——来自hzwer的千题计划(19) DP------区间DP(5) DP------悬线法(2) DP------树形DP(1) DP------概率期望(2) DP------线性DP(5) 【专题系列】(4) 搜索------剪枝(4) 数据结构------分块(1) 数据结构------树剖(2) 数据结构------线段树(8) 数论、数学(5) 未归档(1) 模拟(3) 游记(2) 牛客网(1) 算法------TARJAN(1) 算法------二分答案(1) 算法------并查集(1) 算法------最短路(1) 算法------贪心(2) 算法------高斯消元(3) 题解(2)

/ 注册

全部文章（共103篇）

【区间DP】释放囚犯

貌似和石子合并差不多可能是我见的题太少了，所以都差不多 OK 算法分析首先不难看出这是一道区间DP，那么，按照本蒟蒻的意思区间DP==三个循环 for(int len=2;len<=n;len++) >for(int l=1;l+len-1&l...

区间DP

2018-08-20

0 524

[CodeForces522B] Photo to Remember

某一天，n个朋友在一起聚会，他们已经很久没见了，于是他们决定拍照留念。简单的说，拍照的时候，每个人有一个高度和宽度，第i个的高度和宽度分别是hi和wi。这些人排成一条直线，照片的最小的面积必须包含所有的的人，所以照片的面积是W*H，W是所有人的宽度之和，H是所有人中高度最高的那个人的高度。现在想...

TOPOI 数学、数论

2018-08-20

0 378

【转载】线段树题目2

1.hdu1166 敌兵布阵更新节点,区间求和。 2.hdu1754 I Hate It 更新节点,区间最值. . 3.hdu1698 Just a Hook 成段更新,总区间求和. . 4.hdu1394 Minimum Inversion Number 更新节点,区间求和 . 5.hd...

线段树

2018-08-20

1 551

【题解】【CodeForces712C】Memory and De-Evolution

【题目描述】给定一个边长为xx的正三角形，现在每秒钟你可以改变其中一条边的长度（修改量整数），在改变过程中，每秒钟都需要保证改变后的三角形是合法的，且变成均为正整数。现在需要最终把三角形改变成边长为y的正三角形，请计算至少需要几秒钟。【思路分析】比赛的时候想到了用贪心，但是策略...

TOPOI 数学、数论

2018-08-20

0 408

【转载】线段树区间合并小结

原地址：https://blog.csdn.net/sunyutian1998/article/details/79618316 个人感觉区间合并是线段树各种应用中变形最多也是比较难琢磨的一种 (以下以求01序列中最长连续1为例) tree[cur].left代表以区间左端点为起点的连续段的...

线段树线段树的区间合并

2018-08-20

0 643

【HDU1698】 Just a Hook 【线段树入门】

原题：原题链接题意：（机器翻译的...）让我们将钩子的连续金属棒从1到N编号。对于每次操作，Pudge可以将连续的金属棒（从X到Y编号）改为铜棒，银棒或金棒。钩的总值计算为N个金属棒的值的总和。更确切地说，每种棒的值计算如下：对于每个铜棒，值为1. 对于每个银棒，值为2. 对于每个金棒，值...

线段树

2018-08-20

0 464

【DP】编辑距离

日常吐槽：关于DP，有一种莫名的恐惧...maybe源于与mtw大佬与quantum11大佬，初中时抬老师爬楼梯的经历。。。言归正传：编辑距离【题目描述】设A和B是两个字符串。我们要用最少的字符操作次数，将字符串A转换为字符串B。这里所说的字符操作共有三种： 1、删除一个字符； 2...

简单的DP

2018-08-20

0 424

【权值线段树】离散化介绍（+利用线段树求逆序对）

先介绍一下离散化桶排大家应该知道，就是开一个数组（下标为数值，记录了该数值的出现次数）然后遍历过去如果出现次数不为零，那就输出这些数字，理论时间复杂度可以达到O(N)但是由于内存限制，不能开很大的数组。然而如果某个数列中的数字不要求大小确定，只要求这些数字有相对的大小就够了的话，离散化就有了...

线段树离散化

2018-08-20

0 538

【DP】书的复制

原题链接__戳我噢【思路】（区间）DP F[I][J]表示前i本书分给j个人用的最短时间由于每一次j的状态由比j小的状态得出，所以要先枚举j，然后枚举i，接着枚举上一次抄书的人是谁我觉得，难点在于输出具体见代码压行压到手抽筋 #include<iostream&...

区间DP

2018-08-20

0 478

题解 UVA10587 【Mayor's posters】

先讲一下：dalao @lisuier 发布的前一篇题解严格来讲是有错误的比如下一组数据： 1 3 1 10 1 4 7 10 显然答案是3，然而用lisuier dalao的程序做出来的答案是2（后面会讲错误原因）简单看出这道题用线段树可解 so 我们用离散化+权值线段树（戳这里详解...

线段树

2018-08-20

0 419