题目描述

$n$座高度为$h_i$的山 , 当$j <= i$称$i$能看到$j$时 , 当且仅当不存在$j < k < i$ 使得$i$ $j$的连线经过第$k$座山。
$l$ 到 $r$ 的花费为 能保证所有山都被看见所选定的山的最少数量。
求每个区间 $l$ 到 $r$的花费的异或和。

思路

首先因为只能从每个点往左边看，我们很容易发现，对于每一个区间$l$ 到 $r$, 最右边的点$r$必须被选上。
对此，我们设$p$为在$r$能看到的最左边的点，那么$p-1$的高度一定小于$p$。
那么我们可以设计区间$dp$，以$p$为中间点，左边的数量为$dp[l][p] dp[l][p - 1]$的最小值。
那么得到状态转移方程$dp[l][r] ← min(dp[l][p - 1] , dp[l][p]) + dp[p + 1][r]$。
对于求p，我们发现斜率越小，高度越高。
$l$从右往左开始遍历，当到$l$点斜率比$p$的小时，则$l$成为全新的$p$。（这里可以自己画画图）
然后每次$ans$对$dp$进行异或即可。

时间复杂度

$O(n^2)$

AC代码

#include <bits/stdc++.h>
//#define int long long
using namespace std;
const int N = 5010;

int dp[N][N];
int n , h[N];
int ans;

inline double k(int a , int b){
    return (double)(h[b] - h[a]) / (b - a);
}

inline bool compair(int a , int b , int c){
    return k(a , b) < k(c , b);
}

signed main(){
    ios::sync_with_stdio(false) , cin.tie(0);
    cin >> n;
    for (int i = 1 ; i <= n ; i++){
        cin >> h[i];
        dp[i][i] = 1;
        ans ^= dp[i][i];
    }

    for (int r = 2 ; r <= n ; r++){
        int p = 0;
        for (int l = r - 1 ; l ; l--){
            if(!p || compair(l , r , p)) p = l;
            dp[l][r] = min(dp[l][p - 1] , dp[l][p]) + dp[p + 1][r];
            ans ^= dp[l][r];
        }
    }   

    cout << ans << "\n";
    return 0;
}