谁能帮忙看看~~pku--3378 crazy thairs老是说我Output Limit Exceeded？
Crazy ThairsTime Limit: 3000MS Memory Limit: 65536K
Total Submissions: 2515 Accepted: 538
Description
These days, Sempr is crazed on one problem named Crazy Thair. Given N (1 ≤ N ≤ 50000) numbers, which are no more than 109, Crazy Thair is a group of 5 numbers {i, j, k, l, m} satisfying:
1. 1 ≤ i < j < k < l < m ≤ N
2. Ai < Aj < Ak < Al < Am
For example, in the sequence {2, 1, 3, 4, 5, 7, 6},there are four Crazy Thair groups: {1, 3, 4, 5, 6}, {2, 3, 4, 5, 6}, {1, 3, 4, 5, 7} and {2, 3, 4, 5, 7}.
Could you help Sempr to count how many Crazy Thairs in the sequence?
Input
Input contains several test cases. Each test case begins with a line containing a number N, followed by a line containing N numbers.
Output
Output the amount of Crazy Thairs in each sequence.
Sample Input
5
1 2 3 4 5
7
2 1 3 4 5 7 6
7
1 2 3 4 5 6 7
Sample Output
1
4
21
我的代码:
#include"stdio.h"
#include"stdlib.h"
#define M 50000
int trace(long a[],int x[],int t,int n,long double &count)
{
int i,j,flag=0,z=0,tf=0,c=0,s=0,tmp[5]={0};
if(t>n)
{
//printf("%d ",x[0]);
if(x[0])
{
tmp[c++]=a[0];//printf("tmp:%d ",tmp[0]);
}
for(i=1;i<=n;i++)
{ //printf("%d ",x[i]);
if(c<=5&&x[i])
{
if(a[i]>tmp[c-1]&&a[i]<=n+1)
{
tmp[c++]=a[i];
// printf("tmp:%d c:%d ",tmp[c-1],c);
}//if
}//if
if(c==5&&x[i+1])
{
//printf("\n");
return 0;
}
}//for
if(c==5)
{
count++;
//printf("---------%d ",count);
}//printf("\n");
}//if
else
for(i=0;i<=1;i++)
{
x[t]=1-i;
if(!x[t]&&t!=0)
{
for(j=t-1;j>=0;j--)
if(x[j]==0) z++;
}
if(n-z<4) return 0;
if(x[t]&&a[t]<=n+1&&t!=0)
{
for(j=t-1;j>=0;j--)
{
if(x[j])
{
flag=1;
if(a[t]>a[j]){//printf("* ");
trace(a,x,t+1,n,count);
break;}
}
}//for
if(!flag) trace(a,x,t+1,n,count);
}
else if(!x[t]||t==0) {
//printf("** ");
trace(a,x,t+1,n,count);}
}
return 0;
}
int main()
{
int c,n;
scanf("%d",&n);
while(n)
{
long double count=0;
if(n<5) {printf("%d\n",count);continue;}
long a[M]={0};
int i,j,x[M+1]={0},temp=0;
//g[M]={0};
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
trace(a,x,0,n-1,count);
printf("%.0f\n",count);
scanf("%d",&n);
//getchar();while (scanf("%d",&n )!= EOF )
// n=getchar();
}
return 0;
}
页:
[1]