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

Re:很诡异的错误

Posted by timeloop at 2008-08-04 11:21:00 on Problem 3674
In Reply To:Re:很诡异的错误 Posted by:timeloop at 2008-08-04 11:15:35
这段代码能过样例了,但我说的问题依然存在,而且TLE-__________-
n*logn+11^6*6!的复杂度不够吗?
#include <stdio.h>
#include <math.h>
#include <algorithm>
using namespace std;
int i2;
int a[11][300];
int b[11];
int xz[6];
int pl[6];
int pxz[7]={0,1,2,6,24,120,720};
struct ls
{
	int sh;
	int jc;
}tmp[6];
int yz[11];
int nextorder(int n)
{
    int i=n-2;
    while(pl[i+1]<pl[i]) i--;
	if(i==-1)
	{
		for(i2=0;i2<n;i2++)
			pl[i2]=i2;
		return 0;
	}
    int j=n-1;
    while(pl[j]<pl[i]) j--;
    int t;
    t=pl[i];
    pl[i]=pl[j];
    pl[j]=t;
    i=i+1;
    j=n-1;
    while(i<j)
    {
        t=pl[i];
        pl[i]=pl[j];
        pl[j]=t;
        i++;
        j--;
    }
	return 0;
}
int cmp(int c,int d)
{
	return c>d;
}
int main()
{
/*freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);*/
  int n,i,j,k,t1,t2,t3,cnt,tag,max,t5,sum,j3,k5;
  for(i=0;i<=5;i++)
	  xz[i]=0;
  j3=pow(11.0,6.0);
  while (scanf("%d",&n)!=EOF) 
  {
	  if(n<=6)
	  {
		  if(n==1)
		  {
scanf("%d %d",&t1,&t2);
printf("%d\n",t1);
continue;
		  }
     for(i=0;i<n;i++)
		 scanf("%d %d",&tmp[i].sh,&tmp[i].jc);
	 for(i=0;i<n;i++)
		 pl[i]=i;
	 max=0;
	 for(i=0;i<=pxz[n];i++)
	 {
		 sum=tmp[pl[0]].sh;
		 for(j=1;j<n;j++)
		 {
			 sum+=(tmp[pl[j]].sh/10*tmp[pl[j-1]].jc+tmp[pl[j]].sh);
		 }
		 if(sum>max)
			 max=sum;
		 nextorder(n);

	 }
	 printf("%d\n",max);
	  }
	  else
	  {
	  for(i=0;i<=10;i++)
		  b[i]=0;
   for(i=0;i<n;i++)
   {
	   scanf("%d %d",&t1,&t2);
	   a[t2][b[t2]++]=t1;
   }
for(i=0;i<=10;i++)
sort(a[i],a[i]+b[i],cmp);
/*for(i=0;i<=10;i++)
printf("%d\n",b[i]);*/
t3=0;
max=0;
for(i=0;i<=5;i++)
xz[i]=0;
for(i=1;i<=j3;i++)
{
tag=0;
/*for(j=0;j<=5;j++)
printf("%d ",xz[j]);
printf("\n");*/
for(j=0;j<=10;j++)
yz[j]=0;
for(j=0;j<=5;j++)
yz[xz[j]]++;
for(j=0;j<=10;j++)
if(yz[j]>b[j])
{
	tag=1;
	break;
}
if(tag)
{
xz[0]++;
k5=0;
while(xz[k5]>10&&k5<6)
{
	xz[k5]=0;
	xz[k5+1]++;
	k5++;
}
/*for(j=0;j<=10;j++)
printf("%d ",xz[j]);
printf("\n");*/
continue;
}
t5=0;
for(j=10;j>=0;j--)
for(k=0;k<yz[j];k++)
{
tmp[t5].sh=a[j][k];
tmp[t5].jc=j;
t5++;
}
for(j=0;j<=5;j++)
{
	pl[j]=j;
}
for(k=1;k<=720;k++)
{
sum=tmp[pl[0]].sh;
for(j=1;j<=5;j++)
sum+=(tmp[pl[j]].sh/10*tmp[pl[j-1]].jc+tmp[pl[j]].sh);
if(sum>max)
max=sum;
nextorder(6);
}
xz[0]+=1;
k5=0;
while(xz[k5]>10)
{
	xz[k5]=0;
	xz[k5+1]+=1;
	k5++;
}
/*for(j=0;j<=5;j++)
printf("%d ",xz[j]);
printf("%d",i);
printf("\n");*/
}
printf("%d\n",max);
	  }


  }
  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