40分,求条,用的SQL感谢大佬
查看原帖
40分,求条,用的SQL感谢大佬
1067789
Director_Ni楼主2024/11/26 20:14

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=100009;

int main(){
    int n,k;
    cin>>n>>k;
    ll s[N];ll dp[N];ll sum=0;
    memset(dp,0,sizeof(dp));
    memset(s,0,sizeof(s));
    for(int i=1;i<=n;++i){
        cin>>s[i];
        sum+=s[i];
    }
    k++;deque<int>dq;

    ll ans=sum;

    dq.push_back(0);
    for(int i=1;i<=n;++i){
        
        while(!dq.empty()&&dq.front()<i-k){
            dq.pop_front();
        }
        if(dq.empty()){
            dp[i]=s[i];
        }
        else     dp[i]=s[i]+dp[dq.front()];
        while(!dq.empty()&&s[dq.back()]>s[i]){
            dq.pop_back();
        }
        
        dq.push_back(i);
        
    }
    for(int i=n-k+1;i<=n;++i){
        ans=min(ans,dp[i]);
    }
    cout<<sum-ans;
}

用的思路可能不太正统,就是让在区间内,不选的奶牛效率最小(每个k+1个奶牛都一定有一个不选)

2024/11/26 20:14
加载中...