求助！实在找不出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;
}

• Re:求助！实在找不出WA的原因啊？难道理解错了，还请那位仁兄帮帮忙啊，给几个测试数据也行啊！ (3864) linht 2006-08-26 12:58:34
  • 为什么没有一个热心人呢 !o! (0) linht 2006-08-26 13:01:09