求救!dfs 50分,找不到错因(5个wa:2 6 8 9 10)
查看原帖
求救!dfs 50分,找不到错因(5个wa:2 6 8 9 10)
397565
kewenxuan楼主2021/8/19 20:42

(5个wa:2 6 8 9 10)

#include<bits/stdc++.h>
using namespace std;
int p,ans[20];
int v,need[30];
int g,x[20][30];
int a[20];
void cc()
{
	p=87654321;
	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>>x[i][j];
}
bool is(int l)
{
	int xx[30];
	for(int i=1;i<l;i++)xx[i]=0;
	
	for(int j=1;j<=g;j++)
	{
		for(int i=1;i<l;i++)xx[j]+=x[a[i]][j];
		if(xx[j]<need[j])return 0;
	}
	return 1;
}
void dfs(int dep)
{
	if(dep>p)return;
	if(is(dep)==1)
	{
		p=dep-1;
		for(int i=1;i<dep;i++)ans[i]=a[i];
		return;
	}
	for(int k=a[dep-1]+1;k<=g;k++)
	{
		a[dep]=k;
		dfs(dep+1);
		a[dep]=0;
	}
}
void pr()
{
	cout<<p<<" ";
	for(int i=1;i<=p;i++)cout<<ans[i]<<" ";
}
int main()
{
	cc();
	dfs(1);
	pr();
	return 0;
}

求救诸位神犇

2021/8/19 20:42
加载中...