记忆搜求助!

P1725 琪露诺

log_and_long @ 2023-11-11 10:01:32

???

为啥还是TLE?能优化吗?

#include<bits/stdc++.h>
using namespace std;
int n,a[200005],l,r;
int jy[200005];
int dfs(int x){//x为目前位置;
    if(x+l>n){
        return 0;
    }
    if(jy[x]!=-0x7fffffff) return jy[x];
    int e=min(x+r,n+1);
    for(int i=x+l;i<=e;i++){
        jy[x]=max(jy[x],dfs(i)+a[i]);
    }
    return jy[x];
}
int main(){
    ios::sync_with_stdio(0);
    cin>>n>>l>>r;
    for(int i=0;i<=n;i++){
        cin>>a[i];
        jy[i]=-0x7fffffff;
    }
    cout<<dfs(0);
    return 0;
}

by _mortal_ @ 2023-11-11 10:02:52

本身就是 dp+单调队列优化,你记忆化怎么过


by _mortal_ @ 2023-11-11 10:03:12

@log_and_long


by _Error_and_Bug_ @ 2023-11-11 10:03:14

就是,赞同楼上


|