高度由习惯堆积

分类 算法:计数dp 下的文章

BZOJ2669 局部极小值

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

HDU4532 湫秋系列故事——安排座位

题目 为了给腾讯公司找到更多优秀的人才,HR湫秋最近去某高校组织了一次针对该校所有系的聚会,邀请了每个系的一些优秀学生来参加。   作为组织者,湫秋要安排他们的座位。这并不是一件很简单的事情,因为只有一排位置,并且位置总数恰好等于参加聚会的人数。为了促进交流,两个来自相同系的同学不可以座位相邻。湫秋现在希望知道有多少种不同的合理安排座位的方法(任意两个合理的安排方法,只要有一个位置的同学不...
February 17, 2019

CF568B Symmetric and Transitive

题目有一个集合,它的元素是二元关系(x,y),其中x,y的范围是[1,n]。这个集合满足如下性质:1.如果这个集合里有(x,y),那么一定有(y,x)。2.如果这个集合里同时有(x,y)和(y,z),那么一定有(x,z)。注意,在这条性质里,x,y,z可以相等3.这个集合不同时包含(1,1),(2,2),……(n,n)。问这个集合有多少种组成方式。(当n=3时,有10种方式,为∅, {(1,...
February 17, 2019

CF129E Games with Rectangle

题目In this task Anna and Maria play the following game. Initially they have a checkered piece of paper with a painted n × m rectangle (only the border, no filling). Anna and Maria move in turns and ...