HDU 2476 String painter

MayFlyyh | DP | 2018-08-14
题意:给你一个由小写字母组成的串S,让你变成由小写字母组成的串F,你可以每次将一个区间变成任意一个小写字母,后来的操作可以覆盖原来的区间,求最小操作次数。 |S|<=200 本题与bzoj1260很相似,bzoj1260是给你一个空白串让变成F,本题是在S上修改 bzoj1260的做法: dp[i][j]表示从i到j涂成F[i~j]的最小花费次数 初始化 dp[i][i]=... [阅读全文]

POJ 1239-Increasing Sequences

MayFlyyh | DP | 2018-07-15
有一串数字,在它们之间加逗号来分隔,使之成为一个上升序列。 要求最后一个数尽可能的小,如果有多个满足要求,则使第一个数尽可能大;如果还有多个,则使第二个最大,依此类推。 感觉这是一道很经典的线性DP题(因为做的太少了)。 思路就是首先保证后一个数尽量大于前一个数,一旦满足条件就去找下一个数。 然后就找到了能满足条件的而且最... [阅读全文]
ė 6 没有评论 0

BZOJ 1079[SCOI2008]着色方案

MayFlyyh | DP | 2018-07-12
1079: [SCOI2008]着色方案 Time Limit: 10 Sec Memory Limit: 162 MB Description   有n个木块排成一行,从左到右依次编号为1~n。你有k种颜色的油漆,其中第i种颜色的油漆足够涂ci个木块。 所有油漆刚好足够涂满所有木块,即c1+c2+...+ck=n。相邻两个木块涂相同色显得很难看,所以你希望统计任意两 个相邻木块颜色不同的着色方案... [阅读全文]
ė 6 没有评论 0

BZOJ1426 收集邮票

MayFlyyh | DP, 期望 | 2018-07-12
1426: 收集邮票 Time Limit: 1 Sec Memory Limit: 162 MB Description 有n种不同的邮票,皮皮想收集所有种类的邮票。唯一的收集方法是到同学凡凡那里购买,每次只能买一张,并且 买到的邮票究竟是n种邮票中的哪一种是等概率的,概率均为1/n。但是由于凡凡也很喜欢邮票,所以皮皮购买第k 张邮票需要支付k元钱。现在皮皮手中没有... [阅读全文]

BZOJ1076 [SCOI2008]奖励关

MayFlyyh | DP, 期望 | 2018-07-12
BZOJ 1076: [SCOI2008]奖励关 Time Limit: 10 Sec Memory Limit: 128 MB Description   你正在玩你最喜欢的电子游戏,并且刚刚进入一个奖励关。在这个奖励关里,系统将依次随机抛出k次宝物, 每次你都可以选择吃或者不吃(必须在抛出下一个宝物之前做出选择,且现在决定不吃的宝物以后也不能再吃)。 宝物一共有n种,系统每次抛... [阅读全文]

BZOJ1415 [Noi2005]聪聪和可可

MayFlyyh | DP, 期望 | 2018-07-12
BZOJ1415 [Noi2005]聪聪和可可
BZOJ1415 [Noi2005]聪聪和可可 首先要预处理处当前聪聪在i点,可可在j点的时候聪聪下一步要走到哪里(这我都没想出来。。。 然后就比较简单了,根据套路,这个聪聪在x节点的期望应该是可可在j节点走到各种地方后,聪聪跟上的期望,当然也要算出可可留在原地,聪聪跑两步的期望。最后一加就好了。 一开始是这么想的,可害怕转移的东西互相依赖就没... [阅读全文]

bzoj 1233[Usaco2009Open]干草堆tower

MayFlyyh | DP | 2018-05-16
1233[Usaco2009Open]干草堆tower Description 为了调整牛棚顶的电灯的亮度,Bessie必须建一座干草堆使得她能够爬上去够到灯泡 。一共有N大包的干草(1<=N<=100000)(从1到N编号)依靠传送带连续的传输进牛棚来。第i包干草有一个 宽度W_i(1<=w_i<=10000)。所有的干草包的厚度和高度都为1. Bessie必须利用所有N包干草来建立起干草堆... [阅读全文]

题解 LuoGu P2704 炮兵阵地

MayFlyyh | DP | 2018-03-17
题解 LuoGu P2704 炮兵阵地
#LuoGu P2704 炮兵阵地 司令部的将军们打算在NM的网格地图上部署他们的炮兵部队。一个NM的地图由N行M列组成,地图的每一格可能是山地(用“H” 表示),也可能是平原(用“P”表示),如下图。在每一格平原地形上最多可以布置一支炮兵部队(山地上不能够部署炮兵部队);一支炮兵部队在地图上的攻击范围如图中黑色区域所示: 如果在地图中的灰色所... [阅读全文]

题解 LuoGu P1896 互不侵犯King

MayFlyyh | DP | 2018-03-17
LuoGu P1896 互不侵犯King 题目描述 在N×N的棋盘里面放K个国王,使他们互不攻击,共有多少种摆放方案。国王能攻击到它上下左右,以及左上左下右上右下八个方向上附近的各一个格子,共8个格子。 输入格式: 只有一行,包含两个数N,K ( 1 <=N <=9, 0 <= K <= N * N) 输出格式: 所得的方案数 对于每个格子有两... [阅读全文]

题解 LuoGu P2279 消防局的设立

MayFlyyh | DP, LCA | 2018-03-17
题解 LuoGu P2279 消防局的设立
LuoGu P2279 消防局的设立 题目描述 2020年,人类在火星上建立了一个庞大的基地群,总共有n个基地。起初为了节约材料,人类只修建了n-1条道路来连接这些基地,并且每两个基地都能够通过道路到达,所以所有的基地形成了一个巨大的树状结构。如果基地A到基地B至少要经过d条道路的话,我们称基地A到基地B的距离为d。 由于火星上非常干燥,经... [阅读全文]
Ɣ回顶部