求大佬解答!!!!只过了2个点,其他超时

P1478 陶陶摘苹果(升级版)

Baiwhiter @ 2019-09-21 23:06:56

能有什么优化的方法吗?

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int h[5100],u[5100],n,b,a,s;
bool vis[5100];
int ans=0,maxn=0;;
void dfs(int now,int s){
    if(ans>maxn){
        maxn=ans;
        return;
    }
    if(s==0) return;
    vis[now]=1;
    for(int i=1;i<=n;i++){
        if(!vis[i] && a+b>h[i] && s-u[i]>=0){
            ans++;
            dfs(i,s-u[i]);
            ans--;
        }
    }
    vis[now]=0;
}
int main(){
    cin>>n>>s;
    cin>>a>>b;
    memset(vis,false,sizeof(vis));
    for(int i=1;i<=n;i++){
        cin>>h[i]>>u[i];
    }
    dfs(0,s);
    cout<<maxn<<endl;
    return 0;
} 

by HaveFun @ 2019-09-21 23:07:43

@Baiwhiter 建议思考正解


by R·Buffoon @ 2019-09-22 00:06:57

打表!


|