hdu1480钥匙计数之二解题报告

《hdu1480钥匙计数之二解题报告》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、Hdu1480钥匙计数之二解题报告/*Name:hdu1480Copyright:ecjtu_acm训练基地Author:yimaoDate:17-06-1020:59Description:解题报告*/一、题目ProblemDescription一把钥匙有N个槽，2

2、6300280二、题目分析提交完本题后，颇觉有递推的味道。出发点：构造结果ans[n]=num[1]+……+num[6];其中num[i]表示以i为最后一个槽的高度；计算出num[i]，从而得出结果。首先进行初始化分析，即n=3时。5“相连的槽其深度之差不得为5”——1，6这两个高度不能相邻；而2，3，4，5这四个高度等价，且之后n=4，5，……25的计算过程中均有此规律。即num[1]=num[6]，num[2]=num[3]=num[4]=num[5]，在写代码时注意到这点便可以不需要用到数组；num[1]=num[6]=16;num[2,3,4,5]=1

3、8;ans[3]=104;（下面是重点）再由n-1递推分析n的情况：1、当前面n-1个排列是钥匙的排列，则A、对2，3，4，5作为第n个高度来说都能满足题意，有num[2,3,4,5]=ans[n-1];B、对1，6（1，6等价，记号不同而已）来说，第n-1个高度不能为6，1，即要去掉几个不符合题意的组合；num[1]=ans[n-1]-num__[6](前n-1个中最后一个为6的个数，实际写代码时要用另一个数组保存)。同理num[6]=ans[n-1]-num__[1](……)。也即num[1,6]=ans[n-1]-num__[6](……);2、当前面n-

4、1个排列不是钥匙的排列，则A、对i（i=2，3，4，5）作为第n个高度来说能满足钥匙的要求，则说明前面n-1个排列里仅有两类高度，且与i不同，加上i就刚好3类高度满足题意。那么前面两类高度的选法总数是从其余5类高度里选出两类，即C（5，2），但1，6不能同时选，故组合数为C（5，2）-1。再看排列数，n-1个位置，每个位置可任选两类，但不能全部是同一类高度，故排列数2^(n-1)-2。B、对i=1，6，同上面分析。因为1，6等价，所以我这里举i=1来说，前面两类高度里我有两种取法，选6和不选6。对于选6，组合数是C（4，1）（剩下2，3，4，5任意选一）；再看

5、排列数，每个位置可任选两类，但不能全部是同一高度，且最后一个也即第n-1个位置处不能为6，也可换个说法，最后一个位置放i（i=2，3，4，5），前面n-2个位置任选6和i放，排列数4×2^(n-2)。对于不选6，组合数是C（4，2）；再看排列数，每个位置可任选两类，且不能全部是同一类高度，排列数2^(n-1)-2。5把上面的组合数与排列数相乘便得到一种情况下的num[i]的值，所有情况的值相加便得到结果。三、代码（从简）/*Accepted14800MS192K743BG++*/t[6]=16;ans[3]=104;for(i=4;i<26;i++){//前n

6、-1是钥匙的情况；num[1]=ans[i-1]-t[6];num[2]=ans[i-1];//前n-1不是钥匙的情况；num[1]+=c42*(mult(2,i-1)-2);//不含有6；mult()算阶乘；num[1]+=4*(mult(2,i-2)-1);//含有6；num[2]+=(c52-1)*(mult(2,i-1)-2);ans[i]=2*num[1]+4*num[2];t[6]=num[1];}/*以上代码可以不写mult函数，在数据量大的情况下能省很多时间，请读者自己思考，以上代码可以不写数组，在数据量大的情况下能省内存占用。希望读者完善之*

7、/四、总结(略)刚开始接触这题，有点恐惧，尽管自己手动分析了n=3，4的情况，感觉情况似乎很多种，不敢往下接着想，和以前做这类题一样，以为会有什么很高深的数学公式可以用，就没有继续下去。AC完后就会有似曾相识的感觉，类似于http://acm.hdu.edu.cn/showproblem.php?pid=3284这类由n-1递推到n的题，其实还有好几道，只是一时没找不到，发现这类题的共同点就是选定某个位置作为结果的一部分，用数组保存，n-1到n之间由这个数组来递推。本题hdu1480网上还有一个十分详细的解题报告（http://www.programfan.c

8、om/blog/article.asp