luogu 4909 [Usaco2006 Mar]Ski Lift 缆车支柱 动态规划

可以出模拟赛T1? 

#include <bits/stdc++.h>
#define N 5002  
#define inf 1000000 
#define setIO(s) freopen(s".in","r",stdin) 
using namespace std;     
int f[N],h[N];   
double slope(int i,int j) 
{
    double dx=(double)i-j;   
    double dy=(double)(h[i]-h[j]); 
    if(dy==0) return 0.0;    
    return dy/dx;     
}
int main() 
{ 
    int i,j,n,m;   
    // setIO("input");    
    scanf("%d%d",&n,&m); 
    for(i=1;i<N;++i) f[i]=inf;     
    for(i=1;i<=n;++i) scanf("%d",&h[i]);      
    f[1]=1;    
    for(i=1;i<n;++i) 
    {
        double pre=-100000000000.00;       
        for(j=i+1;j<=n;++j) 
        {
            if(j-i>m) break;       
            double cur=slope(i,j);          
            if(cur>=pre) 
            { 
                pre=max(pre, cur);   
                f[j]=min(f[j], f[i]+1);   
            } 
        }
        // printf("%d %d
",i,f[i]);      
    }    
    printf("%d
",f[n]); 
    return 0;     
}