HDOJ 1290

简介: /* 解题思路: 大神说,将维思考,将三维转换成二维先。 实际上就是问用N个平面分割球体,最多可以分成几部分。 用递推解决。 假设F(n)表示,用n个平面分割球体最多可得的部分数,则F(n)=F(n-1)+f(n-1), f(n-1)表示用n-1条直线分割平面,最多可将平面分割成几部分。
/*
 解题思路:
 大神说,将维思考,将三维转换成二维先。
 实际上就是问用N个平面分割球体,最多可以分成几部分。
 用递推解决。
 假设F(n)表示,用n个平面分割球体最多可得的部分数,则F(n)=F(n-1)+f(n-1),
 f(n-1)表示用n-1条直线分割平面,最多可将平面分割成几部分。
 f(n)=f(n-1)+n【第n条直线与其他直线最多有n-1个交点】。得:f(n)=1+(1+n)*n/2。
 得:F(n)=n-1+(n*n-1)*n/6+2.
 首先,可以通过直观想象1-3个平面最多分空间为几个部分。1个平面最多将空间分为2部分; 2个平面最多将空间分为4部分; 3个平面最多将空间分为8部分。
若要第四个平面将空间分为最多部分,就要它与前三个平面都相交,且交线不重合。则第四个平面与前三个平面都相交,交线不重合,有三条交线,这三条交线都在第四个平面内,那么要想使这四个平面分空间为最多部分就要使这三条交线分一个平面为最多部分。显然,三条直线分一个平面最多为7部分。所以,四个平面分空间数最多为:三个平面最多分平面数加上三条直线最多分平面的部分数:8+7=15。
推广到一般情况,n个平面最多可分空间为f(n)部分,第n个平面与n-1个平面分别相交且交线不重合,问题转化为n-1条直线最多将一个平面分成几部分。
所以:
f(n)=f(n-1)+n(n+1)/2+1
递归得:
f(n)=(n^3 + 5n + 6)/6
 */
 #include<stdio.h>
 #include<math.h>
 int main()
 {
     int n;
     while(scanf("%d",&n)==1)
        printf("%d\n",n-1+(n*n-1)*n/6+2);
     return 0;
 }

 

目录
相关文章
HDOJ 2046 骨牌铺方格
HDOJ 2046 骨牌铺方格
146 0
HDOJ 2046 骨牌铺方格
HDOJ 2802 F(N)
HDOJ 2802 F(N)
95 0
HDOJ 2802 F(N)
HDOJ 2034 人见人爱A-B
HDOJ 2034 人见人爱A-B
126 0
|
安全
HDOJ 2022 海选女主角
HDOJ 2022 海选女主角
150 0
HDOJ 1323 Perfection(简单题)
Problem Description From the article Number Theory in the 1994 Microsoft Encarta: “If a, b, c are integers such that a = bc, a is called a...
843 0
HDOJ 1303 Doubles(简单题)
Problem Description As part of an arithmetic competency program, your students will be given randomly generated lists of from 2 to 15 uniq...
983 0
HDOJ 1412 {A} + {B}
Problem Description 给你两个集合,要求{A} + {B}. 注:同一个集合中不会有两个相同的元素. Input 每组输入数据分为三行,第一行有两个数字n,m(0 < n,m marr[mid]) { System.
773 0
|
机器学习/深度学习
HDOJ 2074 叠筐
Problem Description 需要的时候,就把一个个大小差一圈的筐叠上去,使得从上往下看时,边筐花色交错。这个工作现在要让计算机来完成,得看你的了。 Input 输入是一个个的三元组,分别是,外筐尺寸n(n为满足0< n< 80的奇整数),中心花色字符,外筐花色字符,后二者都为ASCII可见字符; Output 输出叠在一起的筐图案,中心花色与外筐花色字符从内层起交错相叠,多筐相叠时,最外筐的角总是被打磨掉。
838 0