Blog·Tanky WooABOUTRSS

HDOJ 2050 折线分割平面

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

题目地址: http://acm.hdu.edu.cn/showproblem.php?pid=2050 汗,半天没找出递推的关系,看了课件给的2种方法,都不明白。。。 结果去网上参考了别人的,似乎对于** F(n) = F(n-1) + 4(n-1) + 1 **这个方法都不太明白。。。 大部分包括我都是理解的这个方法:

F(n) = 2nn - n + 1

解释:

首先分析直线分平面最多多少份:f(1)=2;f(2)=4;f(3)=7;f(4)=11……可知f(n)=f(n-1)+n且f(1)=2.可知f(n)=(1+n)*n/2+1;

同理,可将每个折线看成是两条直线,但是少了一半。因此每一条折线比两条直线分割的面的部分少2。因此n条折线比2n条直线分割平面形成的部分少2n。所以f(n)=(1+2n)2n/2+1-2n=2*n^2-n+1;

摘至:http://blog.sina.com.cn/s/blog_606e17490100ej8i.html

 // Author: Tanky Woo
// HDOJ 2050
#include 
using namespace std;

int main()
{
    int nCases, num;
    scanf("%d", &nCases;);
    while(nCases--)
    {
        scanf("%d", #);
        printf("%d\n", 2*num*num - num + 1);
    }
    return 0;
}