题解 P4266 【[USACO18FEB]Rest Stops】

Ruo_Xu_void · 2018-12-17 23:20:17 · 题解

其他几个题解我这个蒟蒻没太看看懂，所以写下自己思路: 先比较出美味值最大的休息点，然后只要重复求出从此休息点往后的休息点之中美味值最大的，直到最后一个休息点，然后把每一个记录下来，再分别求出以上每个休息点能获得的最大美味值，以下为代码。（952ms, 3744KB思路过于简单所以快超时了，希望能采纳）

#include<bits/stdc++.h>
using namespace std;
long long x[100010],c[100010],m=0,k,a[100010],b[100010],e=1,l,n,rf,rb,ans=0;
//x,c为输入数据 a,b记录每个最大值
void s(long long u){//递归求出每一个最大值
    e++;
    m=0;
    for(long long j=u+1;j<=n;j++){
        if(c[j]>m){
            m=c[j];
            k=j;
        }
    }
    a[e]=x[k];
    b[e]=c[k];
    if(k!=n){
        s(k);
    }
}
int main(){
    scanf("%lld%lld%lld%lld",&l,&n,&rf,&rb);
    for(long long i=1;i<=n;i++){
        scanf("%lld%lld",&x[i],&c[i]);
        if(c[i]>m){//求第一个最大值
            m=c[i];
            k=i;
        }
    }
    a[1]=x[k];
    b[1]=c[k];
    s(k);
    for(long long i=1;i<=e;i++){ //求最终结果
        if(i>1){
            ans+=(a[i]-a[i-1])*(rf-rb)*b[i];    
        }
        else{
            ans+=a[i]*(rf-rb)*b[i];
        }
    }
    printf("%lld",ans);
    return 0;
}