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

大家来看看这个,太有意思啦,直接从32ms到0ms

Posted by baidu85 at 2009-02-19 22:01:43 on Problem 1190
#include<stdio.h>
#define in(a,b) (a<b?a:b)
int n,m;
int minv[21],mins[21];
int bests;

void dfs(int v,int s,int level,int r,int h)
{
	if(level==0)
	{
		if(v==n && s<bests)
			bests=s;
		return ;
	}
	if(v+minv[level-1]>n || s+mins[level-1]>bests || 2*(n-v)/r+s>=bests)                //如果把中括号内的level-1都换成level就是32ms
		return ;
	int i,j,hh;
	for(i=r-1;i>=level;i--)
	{
		if(level==m)
			s=i*i;
		hh=in((n-v-minv[level-1])/(i*i),h-1);
		for(j=hh;j>=level;j--)
			dfs(v+i*i*j,s+2*i*j,level-1,i,j);
	}
			
}

int main()
{
	int i;
	minv[0]=0;
	mins[0]=0;
	for(i=1;i<=20;i++)
	{
		minv[i]=minv[i-1]+i*i*i;
		mins[i]=mins[i-1]+2*i*i;
	}
	while(scanf("%d%d",&n,&m)==2)
	{
		bests=0x7fffffff;
		dfs(0,0,m,n+1,n+1);
		if(bests==0x7fffffff)
			printf("0\n");
		else
			printf("%d\n",bests);
	}
	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