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 Input3 1
Sample Output6
/**************************************************************
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)