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

假设添加第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）

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

HDU 1249 三角形的分割