首页 > ACM题库 > HDU-杭电 > HDU 1396 Counting Triangles-动态规划-[解题报告] C++
2013
12-09

HDU 1396 Counting Triangles-动态规划-[解题报告] C++

Counting Triangles

问题描述 :

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

输入:

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

process to the end of the file

输出:

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

样例输入:

1
2
3

样例输出:

1
5
13

点击打开链接

根据边长每增加一,正三角和反三角增加的多少进行判断!

#include"stdio.h"
int dp[510]={0,1};
int main()
{
	int i,n;
	for(i=2;i<=500;i++)
	{
		if(i%2==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;
	}
	while(scanf("%d",&n)!=EOF)
		printf("%d\n",dp[n]);
	return 0;
}

解题报告转自:http://blog.csdn.net/yangyafeiac/article/details/7828391


  1. 有两个重复的话结果是正确的,但解法不够严谨,后面重复的覆盖掉前面的,由于题目数据限制也比较严,所以能提交通过。已更新算法

  2. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。