腾讯后台开发2020-视野争夺

题目描述：

方法动态规划：

题目要求求能够覆盖[0,L]范围所用的最少守卫数，创建一个动态规划数组dp记录每个守卫覆盖的边界，dp[i][0]表示第i个守卫左侧覆盖的端点值，dp[i][1]表示第i个守卫右侧覆盖的端点值。

dp[i][0]: 如果xi >= dp[i][0] && yi <= dp[i][1] 表示此时守卫并没有扩展边界，则抛弃该守卫。否则更新更新dp数组边界。此时应判断是否覆盖对应范围，若覆盖则守卫不增加，否则守卫数增加。

另一种情况，xi < dpi][0] && yi > dp[i][0]，此时说明第i个守卫可以覆盖之前所有守卫范围，则抛弃之前所有守卫，将手卫数置为1.

C++代码：

#include
#include
#include
using namespace std;

int lessnumberofguard(vector>& nums,int n,int l){
    vector> dp(n,vector(2,0));
    dp[0][0] = nums[0][0];
    dp[0][1] = nums[0][1];
    cout << dp[0][0] << " " << dp[0][1] << endl;
    int res = 1;
    for(int i=1;i= dp[i-1][0] && nums[i][1] <= dp[i-1][1]){
            continue;
        }else if(nums[i][0] < dp[i-1][0] && nums[i][1] <= dp[i-1][1]){
            if(dp[i][0] == 0 && dp[i][1] >= l){
                res++;
            }
            dp[i][0] = nums[i][0];
            dp[i][1] = dp[i-1][1];
        }else if(nums[i][0] >= dp[i-1][0] && nums[i][1] > dp[i-1][1]){
            if(dp[i][0] == 0 && dp[i][1] >= l){
                res++;
            }
            dp[i][0] = dp[i-1][0];
            dp[i][1] = nums[i][1];
        }else if(nums[i][0] < dp[i-1][0] && nums[i][1] > dp[i-1][1]){
            dp[i][0] = nums[i][0];
            dp[i][1] = nums[i][1];
            res = 1;
        }
    }
    return -1;
}
int main(){
    int n,l;
    cin >> n >> l;
    vector> nums(n,vector(2));
    for(int i=0;i> nums[i][0] >> nums[i][1];
    }
    int res = lessnumberofguard(nums,n,l);
    cout << res << endl;
    return 0;
}