怎么,0分?谢谢!

P1725 琪露诺

Ch35 @ 2022-06-25 20:20:57

且不谈TLE,那WA是从哪来的?

#include<bits/stdc++.h>
using namespace std;
int n,l,r,a[100000],b[100000],cnt,maxx;
void dfs(int z){
    if(z>n){
        maxx=max(cnt,maxx);
        return;
    }
    if(b[z+l]==0){
        if(z+l>n){
        maxx=max(cnt,maxx);
        return;
    }
        cnt+=a[z+l];
        b[z+l]=1;
        dfs(z+l);
        b[z+l]=0;
        cnt-=a[z+l];
    }
    if(b[z+r]==0){
        if(z+r>n){
        maxx=max(cnt,maxx);
        return;
    }
        b[z+r]=1;
        cnt+=a[z+r];
        dfs(z+r);
        b[z+r]=0;
        cnt-=a[z+r];
    }
}
int main(){
    cin>>n>>l>>r;
    for(int i=1;i<=n;i++)cin>>a[i];
    b[0]=1;
    dfs(0);
    cout<<maxx;
    return 0;
}

by Ch35 @ 2022-06-25 20:33:15

我是用dp还是dfs好?


by mzyc_yang2021 @ 2022-07-07 15:21:07

用dp加单调队列优化


|