题解 P5019 【铺设道路】

· · 题解

传送门

看dalao没人用递推，我发个递推的方法吧。。。

其实我觉得递推代码最短了。。

说实话，当时我还觉得这道题挺不简单的。。（因为我没做过2013的那个积木大赛）还是我太蒟了啊。

听说有积木大赛这题后，我就把我的这道题的ac代码原封不动的提交上去，一下子a了（还真是一道题。。）

这道题我用了递推，在考场上推出了一个莫名其妙的式子。大致思路是这样：

用f[i]表示前i个坑所铺设的最少天数

那么要做的只需比较一下当前的a[i]（就是坑的深度）和a[i-1]，分两种情况：

如果a[i]<=a[i-1]，那么在填a[i-1]时就可以顺便把a[i]填上，这样显然更优，所以f[i]=f[i-1];

否则的话，那么在填a[i-1]时肯定要尽量把a[i]一块填上，a[i]剩余的就单独填。。

所以，f[i]=f[i-1]+(a[i]-a[i-1])。

初始化f[1]=a[1]，向后推就行了。

复杂度大概是O(n)

说实话，我当时交上并没有抱什么希望。所以后来我听说我第一题没错后，心里还是挺惊讶的。。。

上我的代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
int n,a[110000],f[110000];
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    f[1]=a[1];
    for(int i=2;i<=n;i++)
    {
        if(a[i]<=a[i-1])
            f[i]=f[i-1];
        else f[i]=f[i-1]+(a[i]-a[i-1]);
    }
    cout<<f[n]<<endl;
    return 0;
}

我觉得挺简单易懂的。。。

其实这代码还可以更短，我们完全可以边输入边计算，这样会更加精简。