动态规划的多维枚举。 题目描述 118号工厂是世界唯一秘密提炼锎的化工厂,由于提炼锎的难度非常高,技术不是十分完善,所以工厂生产的锎成品可能会有3种不同的纯度,A:100%,B:1%...
DP
洛谷 P1436 棋盘分割 题解【搜索】/【区间DP】【前缀和】
为什么正解是DP。。。 题目描述 将一个8×8的棋盘进行如下分割:将原棋盘割下一块矩形棋盘并使剩下部分也是矩形,再将剩下的两部分中的任意一块继续如此分割,这样割了(n-1)次后,...
洛谷 P3953 NOIp2017提高组 逛公园 题解【记忆化搜索】【最短路】
我要是考场上会什么最短路…… 【问题描述】 策策同学特别喜欢逛公园。 公园可以看成一张N个点M条边构成的有向图,且没有自环和重边。其中1号点是公园的入口,N号点是公园的出口,每条...
洛谷 P1356 数列的整数性 题解【DP】【背包】【同余】
找规律啊…… 题目描述 对于任意一个整数数列,我们可以在每两个整数中间任意放一个符号'+'或'-',这样就可以构成一个表达式,也就可以计算出表达式的值。比如,现在有一个整数数列:17...
洛谷 P1270 “访问”美术馆 题解【树形DP】【模拟】【递归】
输入格式不好玩。。。 题目描述 经过数月的精心准备,Peer Brelstet,一个出了名的盗画者,准备开始他的下一个行动。艺术馆的结构,每条走廊要么分叉为两条走廊,要么通向一个展览室...
洛谷 P2389/U19030 电脑班的裁员 题解【贪心】【DP】【堆】
手写堆吊打优先队列系列 题目背景 有一天,ZZY无意中发现了自己三年前出的题(luogu2389 电脑班的裁员),并觉得500的数据太水了,决定加强一波。 苦思冥想之后,ZZY确...
洛谷 P3800 Power收集 题解【DP】【单调队列】
区间最大值转移问题。 题目背景 据说在红雾异变时,博丽灵梦单身前往红魔馆,用十分强硬的手段将事件解决了。 然而当时灵梦在Power达到MAX之前,不具有“上线收点”的能...
[NOI2018省队选拔赛]一双木棋 题解【博弈】【状压DP】【记忆化搜索】
考试的时候什么都不知道。。。 【题面】 题目的关键在于 如何保证状态合法,也就是棋子必须保证被下在一个矩形的右下角,像这样 也就是说,...
洛谷 P4009 汽车加油行驶问题 题解【DP】【枚举】【分层图】
网络流24题里比较水的一道?? 题目描述 给定一个N×N的方形网格,设其左上角为起点◎,坐标为(1,1),X轴向右为正,Y轴向下为正,每个方格边长为1,如图所示。 一辆汽车从起点◎出发驶向右下角...
洛谷 P2736 “破锣摇滚”乐队 Raucous Rockers 题解【搜索】【动态规划】
数据范围比较小,可以搜索,不过也有0ms的背包做法。 题目描述 你刚刚继承了流行的“破锣摇滚”乐队录制的尚未发表的N(1 <= N <= 20)首歌的版权。你打算从中精选一些歌曲,发行M...