Orangeko

分类

技术笔记(2) 未归档(139) 题解(3)

/ 注册

全部文章（共144篇）

P2053 [SCOI2007]修车【zkw费用流】

题目描述同一时刻有 NN 位车主带着他们的爱车来到了汽车维修中心。维修中心共有 MM 位技术人员，不同的技术人员对不同的车进行维修所用的时间是不同的。现在需要安排这 MM 位技术人员所维修的车及顺序，使得顾客平均等待的时间最小。说明：顾客的等待时间是指从他把车送至维修中心...

网络流费用流

2020-04-01

0 489

P1361 小M的作物【网络流】【最小割】

题目描述小M在MC里开辟了两块巨大的耕地A和B（你可以认为容量是无穷），现在，小P有n中作物的种子，每种作物的种子有1个（就是可以种一棵作物）（用1...n编号）。现在，第i种作物种植在A中种植可以获得ai的收益，在B中种植可以获得bi的收益，而且，现在还有这么一种神奇的现象，就是某...

最小割网络流

2020-03-28

0 577

餐巾计划问题【网络流24题】【费用流】【zkw】

题目描述一个餐厅在相继的 NN 天里,每天需用的餐巾数不尽相同。假设第 ii 天需要 r_iri块餐巾( i=1,2,...,N)。餐厅可以购买新的餐巾,每块餐巾的费用为 pp 分;或者把旧餐巾送到快洗部,洗一块需 m 天,其费用为 f 分;或者送到慢洗部,洗一块需 nn 天(n>...

网络流费用流

2020-03-27

0 628

P1231 教辅的组成【网络流】【最大流】

题目背景滚粗了的HansBug在收拾旧语文书，然而他发现了什么奇妙的东西。题目描述蒟蒻HansBug在一本语文书里面发现了一本答案，然而他却明明记得这书应该还包含一份练习题。然而出现在他眼前的书多得数不胜数，其中有书，有答案，有练习册。已知一个完整的书册均应该包含且仅包含...

最大流网络流

2020-03-24

0 650

P3022 [USACO11OPEN]Odd degrees G

题目描述 The cows are being invaded! Their republic comprises N (1 <= N <= 50,000) towns that are connected by M (1 <= M <= 100,000) undir...

DFS

2020-03-24

0 458

P1052 过河【dp】

题目描述在河上有一座独木桥，一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子，青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数，我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点：0,1,…,L0,1,…,L（其中LL是桥的长度）。坐标为00的点表示桥的起...

dp

2020-03-22

0 694

P1156 垃圾陷阱

思路　　用 f [ i ] [ j ] 来表示第 i 个垃圾被扔下时垃圾堆的高度为 j 时能活下去的时间。　　一开始考虑在 j 枚举时间，结果T掉了一个点，反而在高度为１～１００的情况下枚举高度更方便。　　给时间先排序 ( 数据里给出的并不是升序的时间...

dp

2020-03-21

0 718

P1063 能量项链【区间dp】

P1063 能量项链输入输出样例输入 #1<button class="copy-btn lfe-form-sz-middle" data-v&#45...

dp

2020-03-21

0 532

P1026 统计单词个数【dp】

题目描述给出一个长度不超过 200200 的由小写英文字母组成的字母串（该字串以每行 2020 个字母的方式输入，且保证每行一定为 2020 个）。要求将此字母串分成 kk 份，且每份中包含的单词个数加起来总数最大。每份中包含的单词可以部分重叠。当选用一个单词之后，其第一个字母不能再...

dp

2020-03-21

0 517

P1541 乌龟棋【记忆化搜索】

题目背景小明过生日的时候，爸爸送给他一副乌龟棋当作礼物。题目描述乌龟棋的棋盘是一行NN个格子，每个格子上一个分数（非负整数）。棋盘第1格是唯一的起点，第NN格是终点，游戏要求玩家控制一个乌龟棋子从起点出发走到终点。乌龟棋中MM张爬行卡片，分成4种不同的类型（MM张卡...

dp

2020-03-20

0 628