当前位置 博文首页 > u012938183的博客:动态规划第五节课
折线割面
求n条折线分割平面的最大数目。
推导
1条折线可以将平面分成两部分
2条折线可以将平面分成7部分
3条折线可以将平面分成16部分
4条折线可以将平面分成29部分
。。。。。。
就这样我们Ba公式找到了
d p i = d p i ? 1 + 4 ? i ? 3 dp_i=dp_{i-1}+4*i-3 dpi?=dpi?1?+4?i?3
代码
#include <iostream>
#include <cstdio>
using namespace std;
long long dp[100010] = {0, 2, 7};
int main()
{
int n;
scanf("%d", &n);
for(int i = 3; i <= n; i ++)
{
dp[i] = dp[i - 1] + 4 * i - 3;
}
printf("%lld\n", dp[n]);
return 0;
}