Orangeko

未归档

技术笔记(2) 题解(3)

/ 注册

全部文章 / 未归档（共139篇）

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

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

dp

2020-03-19

0 446

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

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

dp

2020-03-19

0 532

P1387 最大正方形【dp】

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

dp

2020-03-19

0 508

P1508 Likecloud-吃、吃、吃 [dp]

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

dp

2020-03-19

0 473

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

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

dp DFS

2020-03-18

0 505

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

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

dp

2020-03-17

0 597

P1378 油滴扩展【搜索】

题目描述在一个长方形框子里，最多有N（0≤N≤6）个相异的点，在其中任何一个点上放一个很小的油滴，那么这个油滴会一直扩展，直到接触到其他油滴或者框子的边界。必须等一个油滴扩展完毕才能放置下一个油滴。那么应该按照怎样的顺序在这N个点上放置油滴，才能使放置完毕后所有油滴占据的总体积最大呢？（不...

搜索

2020-03-17

0 493

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

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

dp

2020-03-14

0 495

E. Sleeping Schedule 【记忆化搜索】

思路　　暴搜 + 记忆化即可。题意　　小v 在第 i 次醒来后（最开始是醒的）的第 a[i] 小时或者 a[i] - 1 小时睡觉，每次睡一天（这个一天的定义是 h 时）。　　令小v 睡觉的时间点为 x ，如果 L ≤ X ≤ R，就睡得好。　　问最多能睡...

dp

2020-03-13

0 527

cf 627 F. Maximum White Subtree【树形dp】

思路　　令黑点点权为 -1 ，白点点权为 1，求最大子树点权和。　　设 f[i] 为包含 i 点的最大子树点权值，如果当前点的最大点权和比当前点父亲的最大点权和小，则更新当前点。　　比较蠢的做法是，分两种情况讨论下，当前点...

dp codeforces

2020-03-12

0 431