首页 > ACM题库 > HDU-杭电 > HDU 1480 钥匙计数之二-递推-[解题报告] C++
2013
12-11

HDU 1480 钥匙计数之二-递推-[解题报告] C++

钥匙计数之二

问题描述 :

一把钥匙有N个槽,2<N<26槽深为1,2,3,4,5,6。每钥匙至少有3个不同的深度且相连的槽其深度之差不得为5。求这样的钥匙的总数。

输入:

本题无输入

输出:

对2<N<26,输出满足要求的钥匙的总数。

样例输出:

N=3: 104
N=4: 904
N=5: 5880
.
.
.
.
.
N=25: 8310566473196300280

hdu 1438 钥匙计数之一

递推方程式如下
1:如果X是钥匙, 则X1/2/3/4也是, 所以a[I]=a[I-1]*4


2: 如果X不是, X2/3是则X由1/4组成, 但要除去全1和全4, 所以a[I]+=(2^(I-1)-2)*2

后缀2或者3加上就成为钥匙的话,必然是没满足需要3个不同深度槽这一项,故X必然由1/4组成


如果X不是 X1/4是。则X=Y(1/4) M=X1/4=Y(4/1)(1/4)


前I-2位可以是1234,但要除去全为1/4的情况 还有就是X是钥匙且X是以1/4结尾
的情况。我们用b[I]数组表示i位时以1/4结尾的的数量

   temp=(4^(i-2)-2^(i-2))* 2 – b[i-1];

则 b[i]=a[i-1]*2+temp;

#include <stdio.h>
#include <math.h>
#define N 35

__int64 a[N], b[N];

int main()
{
    a[2] = 0; b[2] = 0;
    a[3] = 8; b[3] = 4;
    for (int i = 4; i < 32; i++)
    {
        a[i] = 4 * a[i-1];
        a[i] += (__int64)(pow(2.0, i-1) * 2) - 4;
        __int64 temp = (__int64)(pow(4.0, i-2) - pow(2.0, i-2)) * 2 - b[i-1];
        a[i] += temp;
        b[i] = 2 * a[i-1] + temp;
    }

    for (int i = 2; i < 32; i++)
    {
        printf("N=%d: %I64d\n", i, a[i]);
    }
    return 0;
}



hdu1480 钥匙计数之二

设lock[i]表示:有 i个槽的钥匙的个数

设one[i]表示:有 i个槽且左边第一个槽深度为1的钥匙的个数

设two[i]表示:有 i个槽且左边第一个槽深度为2的钥匙的个数

..

..

设six[i]表示:有 i个槽且左边第一个槽深度为6的钥匙的个数



则显然:lock[i]=one[i]+two[i]+ three[i]+four[i]+five[i]+six[i] 



由于易知:one[i]=six[i],two[i]=three[i]=four[i]=five[i]

则可以得到:lock[i]=one[i]*2+two[i]*4 



其中:

one[i]=one[i-1]+two[i-1]+three[i-1]+four[i-1]+five[i-1]+a[i];

=one[i-1]+two[i-1]*4 +a[i]



two[i]=one[i-1]*2+two[i-1]*4 +b[i]



其中,a[i] 和b[i]的含义分别是:

a[i]表示“有 i个槽且左边第一个槽深度为1,同时这种钥匙在除掉第一个槽后不再是钥匙”的钥匙的个数。

例如 123,124,125,134,135,145,126,136,146,156 就属于这种情况。



b[i]表示“有 i个槽且左边第一个槽深度为2,同时这种钥匙在除掉第一个槽后不再是钥匙” 的钥匙的个数。 



分析到这里,可以知道,关键的是求a[i]和b[i],我们可以得到如下表达式:

a[i]=(2^(i-1)-2)*6+(2^(i-2)-1)*4

b[i]=(2^(i-1)-2)*9



其中,a[i] 的各部分的含义如下:

(2^(i-1)-2)*6:

当去掉第一位,后面i-1位只有 (2,3)或者 (2,4) 或者(2,5) 或者(3,4) 或者(3,5) 或者(4,5)两种数字的时候,显然是不合法的钥匙(不满足至少有3个不同的深度),加上第一位的1则显然是一个合格的钥匙。所以后面的数字可以为一个组合中两个数字的任意一个,根据乘法原理i-1位一共有2^(i-1)种组合,当然还需要去掉两种特殊情况,就是后面i-1位完全相同的情况。满足这种条件的一共有上面六种组合,所以得到(2^(i-1)-2)*6。

(2^(i-2)-1)*4:

当去掉第一位,后面i-1位只有 (2,6)或者 (3,6) 或者(4,6) 或者(5,6)两种数字的时候,显然是不合法的钥匙(不满足至少有3个不同的深度),加上第一位的1则“可能”是一个合格的钥匙。因为要注意满足“相连的槽其深度之差不得为5”这个条件,所以,紧跟着1的绝对不能是6,这样,相对于上面的分析,后面i-2位可以是每组中的任意一个,所以有2^(i-2),还要减去1是因为同样要排除后面全部是和第2位一样的数字这样的情况。满足这种条件的一共有上面的四种组合,所以得到(2^(i-2)-1)*4。



b[i] 的含义如下:

(2^(i-1)-2)*9:

当去掉第一位,后面i-1位只有 (1,3)或者 (1,4) 或者(1,5) 或者(3,4) 或者(3,5) 或者(3,6) 或者(4,5) 或者(4,6) 或者(5,6) 两种数字的时候,显然是不合法的钥匙(不满足至少有3个不同的深度),加上第一位的1则显然是一个合格的钥匙。所以后面的数字可以为一个组合中两个数字的任意一个,根据乘法原理i-1位一共有2^(i-1)种组合,当然还需要去掉两种特殊情况,就是后面i-1位完全相同的情况。满足这种条件的一共有上面9种组合,所以得到(2^(i-1)-2)*9。



目前为止,我们可以求出所有的a[i]和b[i],而且知道了递推关系,只要再做一点简单的工作就可以了,那就是还需要初始值,当然,很容易枚举出最简单的情况

one[3]=16;

two[3]=18;



这样,整个问题就解决了。

特别说明:

这种递推的题目,就是从f(i-1) 加一个元素,然后枚举出所有可能的情况,推导到f(i),当然这个题目有点麻烦,但是套路是一样的,大家也可以参考一下以前的special number课件,里面对于hdoj_1133 Buy the Ticket这个题目的分析,里面的思路和这个完全一样。


#include <stdio.h>
#include <math.h>
#define N 35

__int64 one[N], two[N], lock[N], a[N], b[N];

int main()
{
	one[3] = 16; two[3] = 18; lock[3] = 104;
	for (int i = 4; i < 26; i++)
	{
		a[i] = ((__int64)(pow(2.0, i-1))-2) * 6 + 4 * ((__int64)(pow(2.0, i-2))-1);
		b[i] = 9 * ((__int64)(pow(2.0, i-1))-2);
		one[i] = one[i-1] + 4 * two[i-1] + a[i];
		two[i] = 2 * one[i-1] + 4 * two[i-1] + b[i];
		lock[i] = 2 * one[i] + 4 * two[i];
	}

	for (int i = 3; i < 26; i++)
	{
		printf("N=%d: %I64d\n", i, lock[i]);
	}
	return 0;
}


解题报告转自:http://blog.csdn.net/kk806601756/article/details/11764571


  1. 如果两个序列的最后字符不匹配(即X [M-1]!= Y [N-1])
    L(X [0 .. M-1],Y [0 .. N-1])= MAX(L(X [0 .. M-2],Y [0 .. N-1]),L(X [0 .. M-1],Y [0 .. N-1])
    这里写错了吧。

  2. #include <cstdio>
    #include <cstring>

    const int MAXSIZE=256;
    //char store[MAXSIZE];
    char str1[MAXSIZE];
    /*
    void init(char *store) {
    int i;
    store['A']=’V', store['B']=’W',store['C']=’X',store['D']=’Y',store['E']=’Z';
    for(i=’F';i<=’Z';++i) store =i-5;
    }
    */
    int main() {
    //freopen("input.txt","r",stdin);
    //init(store);
    char *p;
    while(fgets(str1,MAXSIZE,stdin) && strcmp(str1,"STARTn")==0) {
    if(p=fgets(str1,MAXSIZE,stdin)) {
    for(;*p;++p) {
    //*p=store[*p]
    if(*p<’A’ || *p>’Z') continue;
    if(*p>’E') *p=*p-5;
    else *p=*p+21;
    }
    printf("%s",str1);
    }
    fgets(str1,MAXSIZE,stdin);
    }
    return 0;
    }

  3. a是根先忽略掉,递归子树。剩下前缀bejkcfghid和后缀jkebfghicd,分拆的原则的是每个子树前缀和后缀的节点个数是一样的,根节点出现在前缀的第一个,后缀的最后一个。根节点b出现后缀的第四个位置,则第一部分为四个节点,前缀bejk,后缀jkeb,剩下的c出现在后缀的倒数第2个,就划分为cfghi和 fghic,第3部分就为c、c

  4. 给你一组数据吧:29 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 1000。此时的数据量还是很小的,耗时却不短。这种方法确实可以,当然或许还有其他的优化方案,但是优化只能针对某些数据,不太可能在所有情况下都能在可接受的时间内求解出答案。