这么写tle俩,为啥嘞?
查看原帖
这么写tle俩,为啥嘞?
53141
芝麻馅儿汤圆楼主2021/8/31 00:17
#include <iostream>
#include <cstdio>
using namespace std;

int min_step = 30;
int v, g;
int total[30];
int need[30];
int forage[30][30];
int path2[30];
int path[30];
int vis[30];

bool checking(int vx)
{
	for(int i = 1; i <= v; i++)
	{
		int sum = 0;
		for(int j = 1; j <= vx; j++)
			sum += forage[path2[j]][i];
		//cout << sum << endl;
		if(sum < need[i])
			return false;
	}
	return true;
}

void dfs(int step)
{
	if(checking(step))
	{
		if(step < min_step)
		{
			min_step = step;
			for(int i = 1; i <= min_step; i++)
				path[i] = path2[i];
		}
		return;
	}
	for(int i = 1; i <= g; i++)
		if(!vis[i])
		{
			vis[i] = 1;
			path2[step+1] = i;
			dfs(step+1);
			vis[i] = 0;
		}
}

int main()
{
	scanf("%d", &v);
	for(int i = 1; i <= v; i++)
		scanf("%d", &need[i]);
	scanf("%d", &g);
	for(int i = 1; i <= g; i++)
		for(int j = 1; j <= v; j++)
			scanf("%d", &forage[i][j]);
	dfs(0);
	printf("%d ", min_step);
	for(int i = 1; i <= min_step; i++)
		printf("%d ", path[i]);
	return 0;
	
}
2021/8/31 00:17
加载中...