HDU 2050 折线分割平面

解题报告：

题目大意：用n条折线最多可以将平面分成多少个部分。

动态规划，当把第n条折线添加到拥有n-1条折线的图里面时，为了尽可能多的分割平面，所以这条折线要与原有的n-1条折线都有交点，交点总数就是2*（n-1），交叉之后总的线段数为4*（n-1)，和两条射线，所以得到新增加的区域数目就是4*（n-1)+1,其中4*（n-1)是通过线段增加的区域，而1是通过两条射线增加的区域数目。得到递推公式就是

DP[n]=DP[n-1]+4*(n-1)+1。

View Code

 1 #include<stdio.h>
 2 __int64 DP[10000+5];
 3 void dabiao(void) {
 4     DP[1]=2;
 5     for(int i=2;i<=10000;++i)
 6     DP[i]=DP[i-1]+4*(i-1)+1;
 7 }
 8 int main() {
 9     int T,n;
10     dabiao();
11     scanf("%d",&T);
12     while(T--) {
13         scanf("%d",&n);
14         printf("%d\n",DP[n]);
15     }
16     return 0;
17 }