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

都说是随机,来个搜索吧

Posted by 1766500102 at 2014-05-26 23:27:56 on Problem 2454
//136K 16MS
#include<iostream>
#include<algorithm>
using namespace std;
struct node
{
	int ord;
	int val;
};
node d[200];
int k,n;
int up,down,s[130];
bool visit[130];
bool dfs(int b,int num,int sum)
{
	if(num==k)
	{
		if(sum>=down&&sum<=up)
		{
			int i;
			for(i=0;i<n;i++)
			{
				if(visit[i])
					printf("%d\n",d[i].ord);
			}
			for(i=0;i<n;i++)
			{
				if(!visit[i])
					printf("%d\n",d[i].ord);
			}
			return true;
		}
		return false;
	}
	if(sum+s[b]-s[b+k-num]<down||sum+s[n-k+num]>up)
		return false;
	for(int i=b;i<n;i++)
	{
		visit[i]=true;
		if(dfs(i+1,num+1,sum+d[i].val))
			return true;
		visit[i]=false;
	}
	return false;
}
bool cmp(const node &x,const node &y)
{
	return x.val>y.val;
}
int main()
{
	int i;
	scanf("%d",&k);
	n=3*k;
	for(i=0;i<n;i++)
	{
		scanf("%d",&d[i].val);
		d[i].ord=i+1;
	}
	sort(d,d+n,cmp);
	for(i=2*k;i<n;i++)
		printf("%d\n",d[i].ord);
	n-=k;
	for(i=n-1;i>=0;i--)
		s[i]=s[i+1]+d[i].val;
	down=500*k+1; up=s[0]-down;
	dfs(0,0,0);
	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