【fjwc2015】三视图

2015年2月4日1,4691

【题目描述】

史蒂夫想在minecraft里盖一座房子,众所周知,minecraft世界主要是由各式各样的立方体组成的。

可惜的是,现在史蒂夫只拿到了建筑图纸的左视图和正视图(如下所示)。请问可能有多少种建筑符合给定的左视图和正视图,答案对10^9 + 9取模。方块不能悬空摆放。

【输入格式】

第一行一个整数n,表示正视图的列数。

第二行n个整数,表示每列能看到的最高的立方体柱的高度。

第三行一个整数m,表示左视图的列数。

第四行m个整数,表示每列能看到的最高的立方体柱的高度。

【输出格式】

一个整数表示答案。

【样例输入】

2

1 1

2

1 1

【样例输出】

7

【数据范围】

对于10%的数据,1 <= n,m <= 5;

对于30%的数据,1 <= n,m <= 10;

对于60%的数据,1 <= n,m <= 25;

对于100%的数据,1 <= n,m <= 50,所有出现的数不超过10^4。

题解

给定一个矩阵每行每列的最大值

求矩阵填数方案

蒟蒻只yy出30分。。。

将每一行/列是否有已有最大值状压

然后枚举每个格子填数

复杂度n^2 2^n

搬运coolinging神犇学长的题解

易得本题中左视图和正视图中数字的顺序是独立的,故可将两行数字排序后处理。

左/正视图中的第i个数字h限制了俯视图中第i行/列的所有格子不超过高度h,且至少有一格高度为h。

第i行第j列的数字的最大值为d[i][j] = min(左视图第i个数字, 正视图第j个数字),即数字范围是[0, d[i][j]]。若将两行数字从小到大排序后,d[i][j]相同的数字会形成一个个L型。易于发现,d[i][j]不同的格子之间是互不影响的。

现在问题简化为求每个L型的填放方案数,设数字的取值范围为[0, h]。“每行/列至少有一个高度为h的格子”的反面是“每行/每列所有格子高度<h”,后者显然比前者好统计(即数字范围为[0,h-1],方案数=h^格子数)。

故采用容斥法求解,先无视每行每列至少有一高度为h的格子这一限制条件,求出一个总方案数,再减去非法的方案数。求解非法的方案数时,枚举共有i行j列不满足条件(使用组合数学求得非法行列的取法总数),则其余行列满足条件。注意其余行列同样构成一个L型,故转化为了子问题,使用动态规划解决。

时间复杂度O((nm)^2 * (n+m))

30分

100待填坑

  • xiaoyinan2015年5月13日 下午6:40 回复

    Orz

    #1