40pts求调
查看原帖
40pts求调
790670
andy09楼主2023/3/4 00:53

不知道什么原因搜不出字典序

#include<bits/stdc++.h>
using namespace std;
int v,g,p=9999999;
int need[26],a[26][26],book[26],now[26],stand[26];
void dfs(int num,int sum)
{
	if(num==g+1)
	{
		if(sum<p)
		{
			for(int i=1;i<=g;i++)
			{
				if(book[i]==1)
				{
					for(int j=1;j<=v;j++)
					{
						now[j]+=a[i][j];
					}
				}
			}
			for(int i=1;i<=v;i++)
			{
				if(now[i]<need[i])return;
			}
			if(sum==p)
			{
				for(int i=1;i<=g;i++)
				{
					if(stand[i]==1&&book[i]==0)return;
					if(stand[i]==0&&book[i]==1)break;
				}
			}
			for(int i=1;i<=g;i++)
			{
				stand[i]=book[i];
			}
			p=sum;
			memset(book,0,sizeof(book));
			memset(now,0,sizeof(now));
			return;
		}
		return;
	}
	book[num]=1;
	dfs(num+1,sum+1);
	book[num]=0;
	dfs(num+1,sum);
}
int main()
{
	cin>>v;
	for(int i=1;i<=v;i++)
	{
		cin>>need[i];
	}
	cin>>g;
	for(int i=1;i<=g;i++)
	{
		for(int j=1;j<=v;j++)
		{
			cin>>a[i][j];
		}
	}
	dfs(1,0);
	cout<<p<<' ';
	for(int i=1;i<=v;i++)	
	{
		if(stand[i]!=0)
		{
			cout<<i<<' ';
		}
	}
	return 0;
}

记录

2023/3/4 00:53
加载中...