dfs求助
查看原帖
dfs求助
511253
_QrSn_楼主2023/1/5 18:01

看标签和题解都说搜索能过,但是#2#5TLE了

测评连接:https://www.luogu.com.cn/record/98754265

求还能怎么优化,还是说这题不能用深搜写

#include<iostream>
#include<bits/stdc++.h>
#define f(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
int v,n,a[35],biao[35]={0},_max=-1000;
int ans=0;
void dfs()
{ 
    bool flag=false;
    for(int i=0;i<n;i++)
    {
        //cout<<ans<<endl;
        if(flag)
        {
            flag=false;
            return;
        }
        if(ans==v)
        {
            _max=ans;
            return;
        }
        if(biao[i]==0)
        {
            if(ans+a[i]>v)
            {
                _max=max(ans,_max);
                flag=true;
                return;
            }
            else 
            {
                ans+=a[i];
                biao[i]=1;
                dfs();
                biao[i]=0;
                ans-=a[i];
            }
        }
    }
}
int main() {
	cin>>v>>n;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    sort(a,a+n);
    dfs();
    cout<<v-_max;
	return 0;
}
2023/1/5 18:01
加载中...