> 求助！实在找不出WA的原因啊？难道理解错了，还请那位仁兄帮帮忙啊，
> 给几个测试数据也行啊！
> 
> 下面是源程序（后面还有一个是它的原版，容易看出思路）：
> #include<stdio.h>
> #include<stdlib.h>
> #include<string.h>
> #include<malloc.h>
> #include<math.h>
> 
> #define N 5000
> #define MAX 70000
> 
> int hadcount(short m,int *p,short *d,int k)
> {
> 	if(d[m])
> 	{
> 		*p=d[m];
> 		return 1;
> 	}
> 	d[m]=k;
> 	return 0;
> }
> 
> int main()
> {
> 	short source[N+1]={0};
> 	short smaller[N+1][1]={{0}};////
> 	short hadcnt[MAX+1]={0},dif[MAX+1]={0},lcnt[MAX+1]={0};
> 	int i=0,j=0,k=0,l=0,l0=0;
> 	int n=0;
> 	int p=0;
> 	__int64 sets_1=0,sets_2=0,sets_3=0,sets_4=0,subnum[N+1]={0};
> 
> 	scanf("%d",&n);
> 	for(i=1;i<=n;i++)
> 	{
> 		scanf("%hd",&(source[i]));
> 	}
> 	
> 	for(i=n;i>=1;i--)
> 	{
> 		if(!hadcount(source[i],&p,dif,i))
> 		{
> 			sets_1++;
> 		}else
> 		{
> 			sets_3-=subnum[p];
> 			for(l=p+1;l<=n;l++)
> 			{				
> 				if(source[p]>source[l])
> 				{
> 					if(hadcount(source[l],&l0,lcnt,l))
> 						continue;
> 					sets_4-=subnum[l];
> 				}
> 			}
> 			dif[source[i]]=i;//
> 			memset(lcnt,0,sizeof(lcnt));
> 		}
> 		for(j=i+1,k=1;j<=n;j++)
> 		{
> 			if(source[i]>source[j])
> 			{
> 				if(hadcount(source[j],&p,hadcnt,k))//
> 				{
> 					continue;
> 				}
> 				sets_3+=smaller[j][0];//////
> 				sets_4+=subnum[j];//////
> 				smaller[i][0]++;
> 				subnum[i]+=smaller[j][0];
> 			}
> 		}
> 		memset(hadcnt,0,sizeof(hadcnt));
> 	}
> 	memset(hadcnt,0,sizeof(hadcnt));
> 	//printf("4 %d\n",sets_4);//
> 	//printf("3 %d\n",sets_3);//
> 	if(sets_4!=0)
> 	{
> 		printf("4 %d\n",sets_4);
> 	}else if(sets_3!=0)
> 	{
> 		printf("3 %d\n",sets_3);
> 	}else
> 	{
> 		for(i=1;i<=n;i++)
> 		{
> 			if(hadcount(source[i],&p,hadcnt,1))
> 			{
> 				continue;
> 			}
> 			sets_2+=smaller[i][0];
> 		}
> 		if(sets_2!=0)
> 		{
> 			printf("2 %d\n",sets_2);
> 		}else
> 		{
> 			printf("1 %d\n",sets_1);
> 		}
> 	}
> 	return 0;
> }
> 
> 这个是由下面这个程序转化过来的，下面这个用了太多的内存存中间结果，但是容易看出思路：
> 
> #include<stdio.h>
> #include<stdlib.h>
> #include<string.h>
> #include<malloc.h>
> #include<math.h>
> 
> #define N 5000
> #define MAX 70000
> 
> int hadcount(short m,int *p,short *d,int k)
> {
> 	if(d[m])
> 	{
> 		*p=d[m];
> 		return 1;
> 	}
> 	d[m]=k;
> 	return 0;
> }
> 
> int main()
> {
> 	short source[N+1]={0};
> 	short *smaller[N+1],subnum[N+1]={0};
> 	short hadcnt[MAX+1]={0},dif[MAX+1]={0};
> 	int i=0,j=0,k=0;
> 	int n=0;
> 	int p=0;
> 	int sets_1=0,sets_2=0,sets_3=0,sets_4=0;
> 
> 	for(i=1;i<=N;i++)
> 	{
> 		smaller[i]=(short *)malloc(sizeof(short)*(N+1));//
> 		memset(smaller[i],0,sizeof(short)*(N+1));//
> 	}/**/
> 	scanf("%d",&n);
> 	for(i=1;i<=n;i++)
> 	{
> 		scanf("%d",&(source[i]));
> 	}
> 	
> 	for(i=n;i>=1;i--)
> 	{
> 		if(!hadcount(source[i],&p,dif,i))
> 		{
> 			sets_1++;
> 		}
> 		for(j=i+1,k=1;j<=n;j++)
> 		{
> 			if(source[i]>source[j])
> 			{
> 				if(hadcount(source[j],&p,hadcnt,k))//
> 				{
> 					continue;
> 				}
> 				smaller[i][k++]=j;//
> 				smaller[i][0]++;
> 				subnum[i]+=smaller[j][0];
> 			}
> 		}
> 		memset(hadcnt,0,sizeof(hadcnt));
> 	}
> 	for(i=1;i<=n;i++)
> 	{
> 		if(hadcount(source[i],&p,hadcnt,1))
> 		{
> 			continue;
> 		}
> 		for(j=1;j<=smaller[i][0];j++)
> 		{
> 			sets_3+=smaller[smaller[i][j]][0];
> 			sets_4+=subnum[smaller[i][j]];
> 		}
> 	}
> 	memset(hadcnt,0,sizeof(hadcnt));
> 	if(sets_4!=0)
> 	{
> 		printf("4 %d\n",sets_4);
> 	}else if(sets_3!=0)
> 	{
> 		printf("3 %d\n",sets_3);
> 	}else
> 	{
> 		for(i=1;i<=n;i++)
> 		{
> 			if(hadcount(source[i],&p,hadcnt,1))
> 			{
> 				continue;
> 			}
> 			sets_2+=smaller[i][0];
> 		}
> 		if(sets_2!=0)
> 		{
> 			printf("2 %d\n",sets_2);
> 		}else
> 		{
> 			printf("1 %d\n",sets_1);
> 		}
> 	}
> 	return 0;
> }
> 

• 为什么没有一个热心人呢 !o! (0) linht 2006-08-26 13:01:09