HDU2050-线切割平面问题-思维+简单dp

发表于 | 分类于 ， | | 阅读次数:

和队友一块做这道题，队友们几乎秒杀，而自己想了很久也没有推导出一个清晰的规律…看了vinacky的线切割平面问题这篇博客后才豁然开朗,个人感觉一道很好的思维题。
题目描述就是求n条折线可以分割平面的最大数目。比如，一条折线可以将平面分成两部分，两条折线最多可以将平面分成七部分。
example

链接

HDU2050

题解

直线切割平面

首先考虑向平面添加直线(简化思维)后的平面分割情况：
(下面假设新添加的直线与已有直线均相交)
当平面上没有直线时，有一个平面；
有１条直线时，没有节点，多出１部分，共２个平面；
有２条直线时，多了１个节点，多出２部分，共４个平面；
有３条直线时，多了２个节点，多出３部分，共７个平面；
…
至此我们便可以直观的思考一下是什么导致了平面的分割，当添加第i条直线时，因为我们总可以使它和前i-1条直线都相交，所以共有i-1个交点，也即第i条直线被分割成了i段，对每一段来说，它都将自己所在的平面重新分割为两部分。所以添加了第i条直线后，最多可以重新多分割出i个平面。
所以原始的１个平面,
添加１条直线后平面数为1+1;
添加２条直线后平面数为1+1+2;
添加３条直线后平面数为1+1+2+3；
…
得到添加n条直线后的平面数公式：$res = 1 + 1 + 2 + 3 + … + n = \frac{n(n+1)}{2} + 1$

V型折线切割平面

V型折线切割平面可以看做同时添加了两条相交直线，但是稍有不同的是，这两条直线的交点有一侧平面合并了,因此而产生的影响是减少了两个平面。

我们仍然可以保证添加的折线与其他折线均有交点，所以添加第i条V型折线时，增加的平面数为：$2*i - 1 + 2*i - 2$
得到添加n条折线后的平面数公式：$$res = 1 + (1 + 2) + (3 + 4) + … + (2n - 1 + 2n) = \frac{2n(2n + 1)}{2} + 1 - 2n$$
于是可以公式直接求解，也可以dp求解

代码

下面给出dp求解代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <cstdio>
#include <cmath>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <set>

using namespace std;
const int maxn = 1e4 + 7;
int n;
long long dp[maxn] = {1, 2, 7};

int main(){
    int c;
    scanf("%d", &c);
    while(c--){
    scanf("%d", &n);
        for(int i = 3; i <= n; i++){
            dp[i] = dp[i - 1] + ２ * i - 1 + 2 * i - 2;
        }
        printf("%lld\n", dp[n]);
        
    }
    return 0;

}