京东笔试编程题：烽火台,动态规划解法

题目：

战争游戏的至关重要环节就要到来了，这次的结果将决定王国的生死存亡，小B负责首都的防卫工作。首都处于一个四面环山的盆地中，周围的n个小山构成一个环，作为预警措施，小B计划在每个小山上设置一个观察哨，日夜不停的瞭望周围发生的情况。
一旦发生外敌入侵事件，山顶上的岗哨将点燃烽烟。若两个岗哨所在的山峰之间没有更高的山峰遮挡且两者之间有相连通路，则岗哨可以观察到另一个山峰上的烽烟是否点燃。由于小山处于环上，任意两个小山之间存在两个不同的连接通路。满足上述不遮挡的条件下，一座山峰上岗哨点燃的烽烟至少可以通过一条通路被另一端观察到。对于任意相邻的岗哨，一端的岗哨一定可以发现一端点燃的烽烟。
小B设计的这种保卫方案的一个重要特性是能够观测到对方烽烟的岗哨对的数量，她希望你能够帮她解决这个问题。
输入
输入中有多组测试数据。每组测试数据的第一行为一个整数n（3 <=n <= 10^6），为首都周围的小山数量，第二行为n个整数，依次表示小山的高度h，（1 <= h <= 10^9）。
输出
对每组测试数据，在单独的一行中输出能相互观察到的岗哨的对数。

样例输入

1
2
5
1 2 4 5 3

样例输出

1
7

分析

使用动态规划方法。
用两个二维数组分别记录，两座山峰顺时针方向和逆时针方向，中间山峰的最大高度。
然后遍历一次山峰对，求出满足条件的对数。既是两座山峰间山峰的最大高度同时小于等于它们，这里是一个环，因此要考虑顺时针和逆时针方向有一个满足条件就可以。

时间复杂度：O（n^2^)

代码:

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<iostream>
#include<vector>
using namespace std;
int main()
{
    int n;
    while (cin >> n) {
        int heights[n];
        vector< vector<int> > dpClock(n , vector<int>(n , 0));   // 顺时针方向，两座山峰间的最大高度
        vector< vector<int> > dpReClock(n , vector<int>(n , 0));   // 逆时针方向，两座山峰间的最大高度
        int res = 0;
        for (int i = 0; i < n; i++) {	// 自己和自己中间是没有的，是0
            cin >> heights[i];
            dpClock[i][i] = 0;
            dpReClock[i][i] = 0;
        }
        for (int i = 0; i < n; i++) {	// 相邻两座山峰中间也是没有山峰的，最大高度是0
            dpClock[i][(i+1)%n] = 0;
            dpReClock[i][(i-1+n)%n] = 0;
        }
        for (int k = 2; k < n; k++) {	// 长度为k+1的山峰链，从3开始
            for (int i = 0; i < n; i++) {	// 山峰链 ： 顺时针：[i,i+k] 逆时针：[i-k, i]
                // （i,i+k）间的最高山峰高度，分两种情况
                // 1. 如果（i,i+k-1）间的最高山峰低于新增加的第i+k-1座山峰，那么更新最大高度为新增加的i+k-1座山峰的高度
                // 2. 否则，依然是(i,i+k-1)间的最大高度
                // 因为是环，所以要做特殊处理，越界时直接mod。
                dpClock[i][(i+k)%n] = heights[(i+k-1)%n] > dpClock[i][(i+k-1)%n] ? heights[(i+k-1)%n] : dpClock[i][(i+k-1)%n];
                // 逆时针方向同理
                dpReClock[i][(i-k+n)%n] = heights[(i-k+1+n)%n] > dpReClock[i][(i-k+1)%n] ? heights[(i-k+1+n)%n] : dpReClock[i][(i-k+1)%n];
            }
        }
        for (int i = 0; i < n; i++) {
            for (int k = 0; k < n; k++) {
            // 排除自己看见自己的情况。
            // 如果两座山峰间，无论逆时针还是顺时针，中间所有山峰的高度都不大于它们两中任意一个，那么计数+1。
                if (i != k && 
                    (dpClock[i][k] <= heights[i] && dpClock[i][k] <= heights[k]
                || dpReClock[i][k] <= heights[i] && dpReClock[i][k] <= heights[k]))
                    res++;
            }
        }
        // 这里注意求的是对数
        cout << res/2 << endl;
    }
    return 0;
}