[动态规划] 世界杯只因

世界杯只因

题目描述

卡塔尔世界杯正在火热进行中，P大富哥李哥听闻有一种叫"肤白·态美·宇宙无敌·世界杯·预测鸡"的鸡品种（以下简称为只因）有概率能准确预测世界杯赛果，一口气买来无数只只因，并把它们塞进了N个只因窝里，但只因窝实在太多了，李哥需要安装摄像头来观测里面的只因的预测行为。
具体来说，李哥的只因窝可以看作分布在一条直线上的N个点，编号为1到N。由于每个只因窝的结构不同，在编号为i的只因窝处安装摄像头，观测范围为a_i，其中a是长为N的整数列，表示若在此安装摄像头，可以观测到编号在 [ i - a_i ,??i + a_i ]（闭区间）内的所有只因窝。
李哥觉得摄像头成本高，决定抠门一下，请你来帮忙看看最少需要安装多少个摄像头，才能观测到全部N个只因窝。作为回报，他会请你喝一杯芋泥波波牛乳茶。

关于输入

第一行：一个正整数，代表有N个只因窝。
第二行给出数列a：N个非负整数，第i个数代表a_i，也就是在第i个只因窝装摄像头能观测到的区间的半径。
数据保证 N ≦ 500000，0 ≦ a_i ≦ N

关于输出

一个整数，即最少需要装的摄像头数量。

例子输入

10
2 0 1 1 0 3 1 0 2 0

例子输出

3

提示信息

由于数据量较大，建议使用scanf进行读入，即
int n;
scanf("%d", &n);
请注意所使用算法的运行效率
彩蛋：只因们很喜欢那个穿着蓝白球衣长得像黄金矿工的10号

解题分析

首先，要确保所有的只因都被摄像头覆盖到，并且要求我们求出这n个只因全部被覆盖到时所需要的最少的摄像头。当然，如果直接就想出动态规划的方法也许不是很容易，但是我们先去分析一下这个问题。对于每一个位置，我们都可以采用两个措施，放摄像头或者不放摄像头。如果放摄像头的话，那么就一个贪心的思想，我们在这个摄像头覆盖范围内都不用去考虑放不放摄像头的事情了，只需要去再找其他的摄像头把其他没覆盖到的只因覆盖即可，但是这样的话又有一个问题了，我们不能确保当前我们放下的摄像头是一个合理的选择，或者说，是一个能够达到最少放置数的一个选择，所以我们需要一边又一边地去规划扫描，所以很自然地会去想动态规划。

但是，又如何去用动态规划去解决此问题呢？定义dp[i]为到i位置所放置的最少摄像头的数量，我们每次都读入摄像头的范围，并确定为边界l,r。那我们不妨假设，我们就在这个位置放摄像头，那么，我们去查看dp[l-1]+1和dp[r]的大小关系，因为按理来说，如果我们放了这个摄像头，那么在l到r这个范围内，我们最大的放置数量应该是dp[l-1]+1，但凡dp[r]>dp[l-1]+1，那就不好了，说明我们在l到r范围内必定存在多放的摄像头，我们去更新这段区间并决策取最小值即可。

为了正确的递归，我们需要设定dp[0]=0; 以及给数组中每个元素都预先设定一个极大值，方便我们去更新。

代码实现

#include <iostream>
#include <cstring>
#define MAXN 500005
using namespace std;

int n,l=0,r=0,dp[MAXN]={0},s=0;

int main(){
    scanf("%d",&n);
    memset(dp,127,sizeof(dp));
    dp[0]=0;
    for(int i=1;i<=n;i++){
        scanf("%d",&s);
        l=max(1,i-s);
        r=min(n,i+s);
        if(dp[r] > dp[l-1]+1)
            for(int j=l;j<=r;j++)
                dp[j]=min(dp[j],dp[l-1]+1);
    }
    printf("%d",dp[n]);
    return 0;
}