BZOJ 1584 [Usaco2009 Mar]Cleaning Up 打扫卫生

MayFlyyh | DP | 2018-08-16
有N头奶牛,每头那牛都有一个标号Pi,1 <= Pi <= M <= N <= 40000。现在Farmer John要把这些奶牛分成若干段,定义每段的不河蟹度为:若这段里有k个不同的数,那不河蟹度为$k*k$。那总的不河蟹度就是所有段的不河蟹度的总和。 求最小不和谐度哇 考虑如果把每一只牛都作为1段,那么不和谐度为n,所以每一段的种类不可能超过$\sqr... [阅读全文]

BZOJ 4033 [HAOI2015]树上染色

MayFlyyh | DP | 2018-08-16
有一棵点数为N的树,树边有边权。给你一个在0~N之内的正整数K,你要在这棵树中选择K个点,将其染成黑色,并 将其他的N-K个点染成白色。将所有点染色后,你会获得黑点两两之间的距离加上白点两两之间距离的和的收益。 问收益最大值是多少。 设dp[i][j]为以i为子树,染j个黑点对全局的贡献 $dp[i][j]=dp[i][j-t]+dp[e][t]+cost$ cost考虑i的儿... [阅读全文]

HDU 5603 D Game

MayFlyyh | DP | 2018-08-16
给一个公差集合{D},再给N个数 1.在当前剩下的有序数组中选择X(X>=2) 个数字 2.检查1选择的X个数字是否构成等差数列,且公差∈{D} ; 3.如果2满足,删除这X个数字 4.重复1-3,直到不能删除更多数字 问最多可以删除多少个数字? N<=300 一眼看去十分复杂,难点1在检验一串数字是否为等差数列,难点2在删除一段数字... [阅读全文]

LOJ #539「LibreOJ NOIP Round #1」旅游路线

MayFlyyh | DP, 倍增 | 2018-08-16
T 城是一个旅游城市,具有n个景点和m条道路,所有景点编号为 1,2,...,n。每条道路连接这n个景区中的某两个景区,道路是单向通行的。每条道路都有一个长度。 为了方便旅游,每个景点都有一个加油站。第i个景点的加油站的费用为 pi,加油量为ci。若汽车在第i个景点加油,则需要花费pi元钱,之后车的油量将被加至油量上限与ci中的较小值。不过如果... [阅读全文]

HDU 5603 D Game

MayFlyyh | DP | 2018-08-14
> 给一个公差集合{D},再给N个数 > 1.在当前剩下的有序数组中选择X(X>=2) 个数字 > 2.检查1选择的X个数字是否构成等差数列,且公差∈{D} ; > 3.如果2满足,删除这X个数字 > 4.重复1-3,直到不能删除更多数字 > 问最多可以删除多少个数字? > N [阅读全文]
ė 6 没有评论 0

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 3156 Interconnect

MayFlyyh | Hash, 期望 | 2018-08-11
现在有n个点,给你m条边,每次随机选2个点连边(可能选已经连过的)并且花费1个代价,求使n点联通的期望最小代价。 本题关心每个联通块的规模,但不关心每个联通块具体的点。 然后根据规模记忆化搜索,因为规模无法正常表示成值,所以每次hash一下当前dp的状态,然后记忆化搜索看是否已经算过并返回答案。 对于每个联通块,有两种情况,一种是和... [阅读全文]

POJ 1201 Intervals

MayFlyyh | 最短路 | 2018-08-11
题意:给m个区间li,ri,再给一个ci,要求在每个区间li-ri种至少选ci个数,求满足条件最小选的数字。 数字值域:0~50000,m<=50000 哎,考虑差分约束,设D[i]表示从0-i满足条件至少选多少个 l-r,至少选C个,即D[r]-D[l-1]>=c,从l-1到r连一条权值为c的边 然后隐藏条件:0<=D[i]-D[i-1]<=1 然后呢?选一个最小的li,跑向最大的ri。 ... [阅读全文]

POJ 3417 Network

MayFlyyh | LCA | 2018-08-11
题意:给你一颗N个节点树,再给你M条新边(保证不与树边重复)。现在求剪短一条树边和任意M边中的一条边,能将树分成两个联通块的方案 > N (1 ≤ N ≤ 100 000), M (1 ≤ M ≤ 100 000) 一开始想的:暴力,N*M然后检验。。 然后想到树形DP,能不能按照每个节点剪掉它与它父亲节点的树边思考 剪掉这条树边,树边部分肯定不与大树相连接 分类讨论一下... [阅读全文]

POJ 1475 Pushing Boxes

MayFlyyh | 搜索 | 2018-07-16
想象您正站在一个二维的迷宫中,迷宫由是正方形的方格组成,这些方格可能被岩石阻塞,也可能没有。您可以向北,南,东或西一步移到下一个方格。这些移动被称为行走(walk)。 在一个空方格中放置了一个箱子,您可以挨着箱子站着,然后按这个方向推动这个箱子,这个箱子就可以被移动到一个临近的位置。这样的一个移动被称为推(push)。除了推以... [阅读全文]
Ɣ回顶部