Orangeko

分类

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

/ 注册

全部文章（共28篇）

P1850 换教室【最短路】【概率DP】

题目描述对于刚上大学的牛牛来说，他面临的第一个问题是如何根据实际情况申请合适的课程。在可以选择的课程中，有 2n2n 节课程安排在 nn 个时间段上。在第 ii（1 \leq i \leq n1≤i≤n）个时间段上，两节内容相同的课程同时在不同的地点进行，其中，牛牛预先被安排在教室 ...

dp

2020-03-14

0 495

P1514 引水入城 [记忆化搜索]

题目描述在一个遥远的国度，一侧是风景秀美的湖泊，另一侧则是漫无边际的沙漠。该国的行政区划十分特殊，刚好构成一个NN 行\times M×M 列的矩形，如上图所示，其中每个格子都代表一座城市，每座城市都有一个海拔高度。为了使居民们都尽可能饮用到清澈的湖水，现在要在某些城市建造水利...

dp

2020-03-17

0 597

P1441 砝码称重【搜索+01背包】

题目描述现有n个砝码，重量分别为 a_iai，在去掉 mm 个砝码后，问最多能称量出多少不同的重量（不包括 00）。请注意，砝码只能放在其中一边。输入格式第 11 行为有两个整数 nn 和 mm，用空格分隔。第 22 行有 nn 个正整数 a_1, a_2,...

dp DFS

2020-03-18

0 505

P1508 Likecloud-吃、吃、吃 [dp]

展开题目背景问世间，青春期为何物？答曰：“甲亢，甲亢，再甲亢；挨饿，挨饿，再挨饿！” 题目描述正处在某一特定时期之中的李大水牛由于消化系统比较发达，最近一直处在饥饿的状态中。某日上课，正当他饿得头昏眼花之时，眼前突然闪现出了一个n*m(n a...

dp

2020-03-19

0 473

P1387 最大正方形【dp】

题目描述在一个n*m的只包含0和1的矩阵里找出一个不包含0的最大正方形，输出边长。输入格式输入文件第一行为两个整数n,m（1<=n,m<=100），接下来n行，每行m个数字，用空格隔开，0或1. ...

dp

2020-03-19

0 508

P1417 烹调方案【泛化物品背包】

题目背景由于你的帮助，火星只遭受了最小的损失。但gw懒得重建家园了，就造了一艘飞船飞向遥远的earth星。不过飞船飞到一半，gw发现了一个很严重的问题：肚子饿了~ gw还是会做饭的，于是拿出了储藏的食物准备填饱肚子。gw希望能在T时间内做出最美味的食物，但是这些食物美味程度的计算方式比...

dp

2020-03-19

0 532

P1855 榨取kkksc03【***01背包】

思路　　在01背包的基础上多枚举一维就好了吧。。。想都没想无脑做的。 CODE

dp

2020-03-19

0 446

P1736 创意吃鱼法【dp】

题目描述回到家中的猫猫把三桶鱼全部转移到了她那长方形大池子中，然后开始思考：到底要以何种方法吃鱼呢（猫猫就是这么可爱，吃鱼也要想好吃法 ^_*）。她发现，把大池子视为01矩阵（0表示对应位置无鱼，1表示对应位置有鱼）有助于决定吃鱼策略。在代表池子的01矩阵中，有很多的正方形子矩阵，如...

dp

2020-03-20

0 553

P1541 乌龟棋【记忆化搜索】

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

dp

2020-03-20

0 628

P1026 统计单词个数【dp】

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

dp

2020-03-21

0 517