hdu 1396 Counting Triangles (递推)

Counting Triangles

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 2012 Accepted Submission(s): 966

Problem Description

Given an equilateral triangle with n the length of its side, program to count how many triangles in it.

Input

The length n (n <= 500) of the equilateral triangle's side, one per line.

process to the end of the file

Output

The number of triangles in the equilateral triangle, one per line.

Sample Input

1 2 3

Sample Output

1 5 13

Author

JIANG, Jiefeng

Source

ZOJ Monthly, June 2003

Recommend

Ignatius.L | We have carefully selected several similar problems for you: 1992 1393 2065 1319 1418

推了一段时间没推出来= =！

 1 //15MS    232K    347 B    C++
 2 /*
 3 
 4 递推:
 5      a[n] = a[n-1] + n * (n + 1) / 2; 
 6 
 7 还有一种情况是最底下一行顶角朝下的三角形： 
 8 观察规律得:left = (n-1) + (n-1)-2 + (n-1)-4... + last(n为奇数, last为2, 反之为1)
 9     
10     a[n] = a[n] + left;
11      
12 
13 */
14 #include<stdio.h>
15 int main(void)
16 {
17     __int64 ans[505]={0,1};
18     for(int i=2;i<=500;i++){
19         ans[i]=ans[i-1]+i*(i+1)/2;
20         int k=i-1;
21         while(k>0){
22             ans[i]+=k;
23             k-=2;
24         }
25     }
26     int n;
27     while(scanf("%d",&n)!=EOF)
28     {
29         printf("%I64d
",ans[n]);
30     }
31     return 0;
32 }