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

题目描述

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

 title=

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;
}