高度由习惯堆积

Hnoi2010 City 城市建设

题目PS国是一个拥有诸多城市的大国,国王Louis为城市的交通建设可谓绞尽脑汁。Louis可以在某些城市之间修建道路,在不同的城市之间修建道路需要不同的花费。Louis希望建造最少的道路使得国内所有的城市连通。但是由于某些因素,城市之间修建道路需要的花费会随着时间而改变,Louis会不断得到某道路的修建代价改变的消息,他希望每得到一条消息后能立即知道使城市连通的最小花费总和, Louis决定...

BZOJ2669 局部极小值

题目有一个n行m列的整数矩阵,其中1到nm之间的每个整数恰好出现一次。如果一个格子比所有相邻格子(相邻是指有公共边或公共顶点)都小,我们说这个格子是局部极小值。给出所有局部极小值的位置,你的任务是判断有多少个可能的矩阵。思路看到数据范围马上想到状压dp。先分析状态数,会发现局部极小值在一张图中最多只有8个,所以状态为已经实现了哪些局部极小值。$dp[i][S]$为已经填完数$[1,i]$,满...

BZOJ2574 Store-Keeper

题目题目地址思路仔细分析一下会发现,其实此题的状态数并不多,只有$100*100*4$种,人的移动是不需要的,也就是说,我们只需要知道当箱子在某一个位置时,人能不能从箱子的一个侧面走向另一个侧面。转化成图论模型也就是说,当一个无向图断掉一个点之后,判断两个点的连通性。这就让人想到了COCI2006/2007 Final的题,这是那道题的一个子问题。首先用$Tarjan$将$dfs$树建立出来...

POI2006 ZAB-Frogs

题目一群青蛙正在摧毁Byteotia所有的庄稼. 一个叫Byteasar的农夫决定使用一种放在田里的奇特的"scarefrogs"来吓跑他们, 所有的青蛙在跳跃过程中都尽量使自己离他们越远越好, 即是让自己离最近的scarefrog越远越好. Byteasar的田是块矩形的土地. 青蛙们跳跃的方向平行于坐标轴并且每次跳跃的距离为1. 一条跳跃路线的scarefrogs-距离为路径上所有点距离...