文章

10

粉丝

168

获赞

0

访问

51.6k

头像
DFs
P1164 清华大学上机题
发布于2022年3月6日 20:18
阅读数 4.8k

#include<bits/stdc++.h>
using namespace std;
const int N=25;
int n,m;
int a[N];
int q[N];
int ans;

void dfs(int idx,int rest,int num){
	if(rest==0){
		ans=min(ans,num);
		return ;
	}
	if(idx==0)	return ;
	if(q[idx]<rest)	return ;
	if(q[idx]==rest){
		ans=min(ans,num+idx);
		return ;
	}
	if(rest>=a[idx])	dfs(idx-1,rest-a[idx],num+1);
	dfs(idx-1,rest,num);
}

int main(){
	while(cin>>m>>n){
		for(int i=1;i<=n;i++)
			cin>>a[i];
		for(int i=1;i<=n;i++)
			q[i]=q[i-1]+a[i];
		ans=1e9;
		dfs(n,m,0);
		if(ans==int(1e9))	cout<<0<<'\n';
		else	cout<<ans<<'\n';
	}
	return 0;
}

 

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发