HDU 1249 三角形的分割

可以将三角形的三条边一条一条加进图形中观察

假设添加第n个三角形

前n-1个三角形将区域划分为sum[n-1]

第n个三角形每条边最多能经过前n-1个三角形每条三角形的两条边 ， 一条边切完增加了 2*(n-1)-1个区域

那么三条边切完内部图形增加了6*(n-1)-3个区域，而新三角形本身在三个顶角形成了三个新的区域

就共增加了6*(n-1)个区域

那么递推函数就是

sum[i] = sum[i-1] + 6*(i-1)

其实说的直接点就是利用欧拉公式解决问题

V(点) - E(边) + F(面） = 2

每次添加第n个三角形

增加的点为 2 * （n-1） * 3  + 3 = 6*n-3

增加的边为 （2*n - 1）*3（新三角形增加的边） + 3*（n-1）*2（原n-1个三角形每个三条边都被新三角形分割了两次） = 6*n-9

所以最后增加的面数为 6*（n-1）

 #include <cstdio>

 int sum[];

 int main()

 {

     sum[] = ;

     for(int i =  ; i<=  ; i++)

         sum[i] = sum[i-] + **(i-);

     int T , n;

     scanf("%d" , &T);

     while(T--){

         scanf("%d" , &n);

         printf("%d\n" , sum[n]);

     }

     return ;

 }