首页 > 代码库 > HDU 1396 Counting Triangles 递推
HDU 1396 Counting Triangles 递推
题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=1396
题目大意：
给你个如图n层的三角形， 问里面总共有多少个三角形。
题目分析：
其实里面的三角形可以分为2种， 一种顶尖朝上，即 △， 另一种 即 ▽。
假设第n层
1.之前所有（n-1）层的所有三角形 dp[n-1]
2.这一层增加的所有 △， 增加 底边长为的的有 n个， 增加底边长为 2的有 n-1个 .......底边长为n的有 1个
因此总共有 n*(n-1)/2 个 △增加了。
3.求所增加的 ▽， 增加底边长为1的 ▽有 n-1个， 增加底边长为2的 ▽有n-3个....
我们求出所有 ▽的个数，判定 n-k >0 就加上， 为负数就结束。
1 #include <iostream> 2 #include <queue> 3 #include <cstdio> 4 #include <cstring> 5 #include <cstdlib> 6 #include <stack> 7 #include <algorithm> 8 #include <vector> 9 #include <string>10 #include <cmath>11 using namespace std;12 const long long maxn =505;13 const long long INF = 0xfffffff;14 int main()15 {16 int n, dp[maxn] = {0,1};17 for(int i=2; i<maxn; i++)18 {19 dp[i] = dp[i-1] + i*(i+1)/2;20 int k = i-1;21 while(k >= 0)22 {23 dp[i] += k;24 k -= 2;25 }26 }27 28 while(cin >> n)29 {30 cout << dp[n] << endl;31 }32 33 return 0;34 }
HDU 1396 Counting Triangles 递推
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。