BZOJ1197: [HNOI2006]花仙子的魔法

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 1463  Solved: 829
Description

相传,在天地初成的远古时代,世界上只有一种叫做“元”的花。接下来,出 现了一位拥有魔法的花仙子,她能

给花附加属性,从此,“元”便不断变异,产生了大千世界千奇百怪的各种各样的花。据说,花仙子既可存在于二

维空间(平 面),又可存在于三维空间(立体),还可存在于n维空间(想象)。二维空间的点可用向量(x1,x2

)表示,三维空间的点可用向量(x1,x2,x3)表 示,一般来说,n维空间的点可用向量(x1,x2,…,xn)表示。而n

维空间中两点(x1,x2,…,xn)与(w1,w2,…,wn)之间的距离定义为

在n维空间中,花仙子每实施魔法就要选择一个参考点(w1,w2,…,wn)和一个作用半径r,并且参考点的位置和作

用半径的大小可以任意选择。这时,n 维空间中所有与参考点(w1,w2,…,wn)之间的距离小于作用半径r的花都会

受到这次魔法的影响。每次魔法都会给受到影响的花带来不同的属性,且的效 果可以叠加。一般来说,若花仙子

总共实施了m次魔法,则n维空间中处于某点的花所具有的属性可用长度为m的二进制串a1a2…am来描述,其中对 1

≤i≤m,若该花受到第i次魔法的影响,则ai的值为1,否则为0。显然,不同的属性对应不同的花。 现在的问题是

:花仙子在n维空间中实施了m次魔法后,最多能得到多少种不同的花?

Input

包含两个整数,并用一个空格隔开,

第一个整数表示实施魔法的次数m,第二个整数表示空间的维数n。

其中,1≤m≤100,1≤n≤15。

Output

仅包含一个整数,表示花仙子在n维空间中实施了m次魔法后,最多能得到多少种不同的花。

Sample Input

3 1

Sample Output

6

/**************************************************************

    Problem: 1197

    User: ictsing

    Language: C++

    Result: Accepted

    Time:8 ms

    Memory:1300 kb

****************************************************************/

 

//1197: [HNOI2006]花仙子的魔法

/*

若干个n维球体最多能把n维空间分为多少部分。

 

1维:1,2,4,6,8,10…(显然)

二维:1,2,4,8,14,22….(我是手花的)

观察后可知f[i][j]=f[i][j-1]+f[i-1][j-1]

 

对于一个n维的球体,去和m-1个其他的球相交,相交处必然是n-1维的球面

令f[i][j]表示 j个i维的物体最多能把空间分成几份,每增加一个球,增加的空间就是j-1个i-1维的球将空间分的份数

j-1个球本来将空间分成了f[i][j-1] 因此f[i][j]=f[i][j-1]+f[i-1][j-1]

*/

#include <cstdio> 

#include <iostream>

using namespace std;

typedef long long ll;

ll f[15+1][100+1];  

inline int read()

{

    int num=0,flag=1;

    char ch;

    do{

       ch=getchar();

       if(ch=='-') flag=-1;

    }while(ch<'0'||ch>'9');

    do{

       num=num*10+ch-'0';

       ch=getchar();

    }while(ch>='0'&&ch<='9');

    return num*flag;

}

int main()

{  

    int m=read(),n=read(); 

    for(int i=1;i<=m;i++) f[1][i]=i*2;  

    for(int i=1;i<=n;i++) f[i][1]=2;  

    for(int i=2;i<=n;i++)  

        for(int j=2;j<=m;j++) 

            f[i][j]=f[i][j-1]+f[i-1][j-1];  

    printf("%lld",f[n][m]);  

    return 0;  

}  

 


评论(1)

热度(4)