Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

dfs(超时) C++

Posted by freelark at 2016-12-04 17:40:23 on Problem 1015
#include<iostream>
#include<stdlib.h>
#include<vector>
using namespace std;

int n, m, total=0;
int dx_min=-1, dx_max, d,p;
vector<vector<int> > judge;
vector<int>select,jury;

void dfs(int pi,int di, int dep)
{
	for (int i = 0; i < n-m+dep+1; i++)
	{
		if (select.size()==0 || i>select.back())
		if (!judge[i][2])
		{
			select.push_back(i);
			pi += judge[i][0];
			di += judge[i][1];
			judge[i][2] = 1;
			if (dep == m - 1)
			{
				if (dx_min == -1 || abs(di - pi) < dx_min)
				{
					dx_min = abs(di - pi);
					dx_max = di + pi;
					d = di;
					p = pi;
					jury.clear();
					for (int j = 0; j<m; j++)
						jury.push_back(select[j]);
				}
				if (abs(di - pi) == dx_min && (di + pi)>=dx_max)
				{
					dx_max = di + pi;
					d = di;
					p = pi;
					jury.clear();
					for (int j = 0; j<m; j++)
						jury.push_back(select[j]);
				}
			}
			if (dep < m - 1)	dfs(pi, di, dep + 1);
			select.pop_back();
			pi -= judge[i][0];
			di -= judge[i][1];
			judge[i][2] = 0;
		}		
	}
}
int main(void)
{
	int di, pi;
	vector<int> temp;
	while (cin >> n >> m)
	{
		if (n + m == 0) break;
		total++;
		judge.clear();
		select.clear();
		dx_min = -1;
		for (int i = 0; i < n; i++)
		{
			temp.clear();
			cin >> pi >> di;
			temp.push_back(pi);
			temp.push_back(di);
			temp.push_back(0);//标志位
			judge.push_back(temp);
		}
		dfs(0, 0, 0);
		cout << "Jury #" << total << endl;
		printf("Best jury has value %d for prosecution and value %d for defence:\n", p,d);
		for (int i = 0; i<m; i++)
			cout<<" "<<jury[i]+1<<" ";
		cout << endl << endl;
	}
	system("pause");
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator