题目地址：
汗，半天没找出递推的关系，看了课件给的2种方法，都不明白。。。
结果去网上参考了别人的，似乎对于 F(n) = F(n-1) + 4(n-1) + 1 这个方法都不太明白。。。
大部分包括我都是理解的这个方法：
F(n) = 2*n*n – 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+2*n)*2*n/2+1-2*n
=2*n^2-n+1；
| 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| // Author: Tanky Woo
// HDOJ 2050
#include
using namespace std;
int main()
{
int nCases, num;
scanf("%d", &nCases);
while(nCases--)
{
scanf("%d", &num);
printf("%d\n", 2*num*num - num + 1);
}
return 0;
} |
阅读(1380) | 评论(0) | 转发(0) |
