首页 > 代码库 > hdu 1396 Counting Triangles (递推)

hdu 1396 Counting Triangles (递推)

2024-07-02 09:30:26   233人阅读

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\n",ans[n]);
30     }
31     return 0;
32 }

 


联系
我们