Question

杭电ACM2037（今年暑假不AC）。 谁能帮我解释下这个代码，从别人那拷过来的。看不懂，再次谢谢大家了。

#include <stdio.h>

int main()
{
int i,j,k,n,a[101],b[101],l,m[101],p,o,t,d;
while(scanf("%d",&n)!=EOF&&n!=0)
{
for(i=0;i<n;i++)
{
scanf("%d%d",&a[i],&b[i]);
}
for (i=1; i<n; i++)
{
for (j=0; j<n-i; j++)
{
if (b[j]>b[j+1])
{
k=a[j];l=b[j];
a[j]=a[j+1];b[j]=b[j+1];
a[j+1]=k;b[j+1]=l;
}
}
}
int A[101]={0};
for(i=0;i<n;i++)
{
d=i-1;
int p=0;
while(d>=0)
{
if(a[i]>=b[d])
{
if(p<A[d])
p=A[d];
}
d--;
}
A[i]=p+1;
}
int t=A[0];
for(i=0;i<n;i++)
if(t<A[i])
t=A[i];
printf("%d\n",t);

}
return 0;
}

Answer 1

这是贪心算法。。。
不妨用Begin[i]和End[i]表示事件i的开始时刻和结束时刻。则原题的要求就是找一个最长的序列a1<a2<…<an，满足：
Begin[a1]<End[a1]<=…<= Begin[an]<End[an]
可以证明，如果在可能的事件a1<a2<…<an中选取在时间上不重叠的最长序列，那么一定存在一个包含a1（结束最早）的最长序列。
（证明：略）

要对结束时间从小到大 排下序。。

楼主可以去HDOJ论坛下载 贪心算法的课件。。
课件下载地址： http://acm.hdu.edu.cn/forum/read.php?tid=3315
这是里面的一道例题。。

Answer 2

出区别。

AC的应该输出1
WA的却输出了0

原因是WA的程序里面并没有定义c[0]，所以当M==N的时候，c[n-m]会访问一个未知大小的变量，导致了当M==N的时候，输出结果不可预计。