首页 > 代码库 > HDU 献给杭电五十周年校庆的礼物 1290 递推
HDU 献给杭电五十周年校庆的礼物 1290 递推
题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=1290
题目大意：
n刀最多可以把一块蛋糕切多少块
题目分析：
假如我们按照立体考虑的话，这题就非常不容易作， 我们的思维是 降低题目的维度。
1.首先我们要明白，蛋糕每多出一个面，就会将这个蛋糕多分出来一块
2.我们一刀下去是一个平面，但是其余的平面会与这个新增的平面相交，会在这个新增的平面上产生n-1条线， n-1条线 最多能把平面分为多少份，
所求的就是我我们新增的平面数，我们就可以求出新增的块数。
3.我们知道 n个平面最多将平面分为 n*（n-1）/2 + 1 份
因此我们的 切蛋糕的递推公式为 dp[n] = dp[n-1] + n*(n-1)/2 +1
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 =1005;13 const long long INF = 0xfffffff;14 15 int main()16 {17 int dp[maxn] = {1}, n;18 for(int i=1; i<maxn; i++)19 dp[i] = dp[i-1] + i*(i-1)/2 + 1;20 while(cin >> n)21 {22 cout << dp[n] << endl;23 }24 return 0;25 }
HDU 献给杭电五十周年校庆的礼物 1290 递推
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。