dfs80分,求助!
查看原帖
dfs80分,求助!
1159868
fire_flower楼主2024/8/29 09:38

蒟蒻不会打dfs啊QAQ 好不容易练习一下tle了好难受

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,a[30],v,s,use[30],ans=INT_MAX;bool flag;
bool cmp(int a,int b){
	return a>b;
}
void dfs(int v){
	if(v<ans)ans=v;
	if(v==0)return ;
	for(int i=0;i<n;i++){
		if(i!=0&&a[i]==a[i-1]&&use[i-1])continue;
		if(!use[i]&&a[i]<=v){
			use[i]=1;
			dfs(v-a[i]);
			use[i]=0;
		}
	}
}
int main(){
	ios::sync_with_stdio;
	cin>>v>>n;
	for(int i=0;i<n;i++){
		cin>>a[i];
		s+=a[i];
	}
	if(v>s){
		cout<<v-s;
		return 0;
	}
	sort(a,a+n,cmp);
	dfs(v);
	cout<<ans;
	return 0;
} 
2024/8/29 09:38
加载中...