这篇博客是从旧博客 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;
}