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加单调队列优化