题解 P4909 【[Usaco2006 Mar]Ski Lift 缆车支柱】

· · 题解

一道有趣的DP题

首先呢，我们可以想到一个dp式:

关键点在于，如何计算i是否可以到达j 我们发现，如果$i$可以到达$j$，则对于$i$，$j$任意一点$k$，都有 $$ h[k]-h[i]\leq h[j]-a[i] (\text{h[i]为i点的纵坐标})

所以如果i不能到达j，那么也不能到达j后面

然后代码就很好写了：

#include <bits/stdc++.h>
#define For(i,x,y) for (int i=x;i<=y;i++)
using namespace std;
typedef double db;
db h[5005];
int f[5005];
int main()
{
    int n,m;
    cin>>n>>m;
    For(i,1,n) cin>>h[i];
    memset(f,0x3f,sizeof(f));
    f[1]=1;
    For(i,1,n)
    {
        db maxx=-1e9;
        For(j,i+1,min(i+m,n))
        {
            db cur=(h[j]-h[i])/(j-i);
            if (cur>=maxx)
            {
                f[j]=min(f[j],f[i]+1);
                maxx=cur;
            }
        }
    }
    cout<<f[n]<<endl;
    return 0;
}