Blog·Tanky WooABOUTRSS

HDOJ 1290 献给杭电五十周年校庆的礼物

08 Aug 2010
这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。

题目地址: http://acm.hdu.edu.cn/showproblem.php?pid=1290


汗了...一向认为自己的空间感很好。。。可是,这题看了解答还是有点迷糊。。。 Analysis: 首先,可以通过直观想象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 
using namespace std;
int main()
{
    __int64 a[1001]={0,2,4,8};
    int i;
    for(i=4;i<1001;i++)
    {
        a[i]=a[i-1]+i*(i-1)/2+1;
    }
    while(scanf("%d",&i;)!=EOF)
    {
        printf("%I64d\n",a[i]);
    }
    return 0;
}