折线分割平面 题解

这题是XJOI上看到的……不过HDU上也有：折线分割平面

题目描述

一条折线最多将平面划分成2个部分 两条折线最多将平面划分成7个部分

n 条折线最多将平面划分成几个部分 ？

输入格式

输入一个整数 n。

输出格式

输出一个整数。

输入输出样例

输入样例

2

输出样例

7

约定

1<=n<=10000

题解

第一步我们有个贪心想法：要使加上第i个折线分割出的区域最多，则要使加上第i-1条折现分割出区域最多。

首先我们可以观察发现：对于已经有 i-1 条折现“最优分割”了一个平面（就是说把这个平面分成尽量多的区域），那么如果加上一条直线，这条直线一定最多只能与 $2(i-1)$ 条直线相交。（因为折线可以分成两条直线，我们这里直接讨论直线）

为了使这条直线加上后能有更多区域变多，我们要让这条直线与尽量多直线相交。如果它与 2i-2 条直线相交，那么它经过了 2i-1 个区域，则它一定把这些平面都一分为二了。

由此我们可以知道：一条直线在原来 i-1 条折线的基础上可以为其增加 2i-1 个区域。那么第i个折线由两条直线构成，最多可以增加 4i-2 个折线。

但是！！！一条折线和两条直线其实是不一样的，因为 X 形的两条相交直线可以把平面分成四个区域，但是 V 形的折线只能分成两个区域！仔细思考可以发现，其实总共多算了一个区域。X和V相差的明明是两个区域，为什么说只多算了一个呢？原因是，在 V 的尖尖头上面有一面块区域是重复算的！

所以递推式就是：

$\displaystyle F(i)=F(i-1)+4i-1$

这样求解就很简单了～

参考代码

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int maxn=10005;
int n,ans=0;
int main(){
    scanf("%d",&n);
    ans=2;
    for (int i=2;i<=n;i++) ans+=4*i-3;
    printf("%d\n",ans);
    return 0;
}