[恢]hdu 1396

2011-12-21 09:23:36

地址：http://acm.hdu.edu.cn/showproblem.php?pid=1396

题意：边长为n的大三角形含有边长大于等于1的小三角形多少个。

mark：递推，分奇偶。考虑增加一列新的底边三角形时，头冲下的三角形和头冲上的三角形增加了多少个。

代码：

# include <stdio.h>



int dp[510]= {0, 1} ;


void init()
{
    int i ;
    for (i = 2; i <= 500 ; i++)
    {
        if (i & 1)
            dp[i] = dp[i-1] + (i*i-1)/4 + i*(i+1)/2 ;
        else
            dp[i] = dp[i-1] + (i*i)/4 + i*(i+1)/2 ;
    }
}


int main ()
{
    int n ;
    init() ;
    while (~scanf ("%d", &n))
        printf ("%d\n", dp[n]) ;
    return 0 ;
}