Question

hdu 1025 不知道为什么老是wa。。 大牛们帮忙看看吧。！ http://acm.hdu.edu.cn/showproblem.php?pid=1025

#include<iostream>
using namespace std;
long u,n;
long a[510001],b[510001],f[510001];
void pai(long,long);
void work(long,long,long);
void work(long p,long l,long r)
{
long mid;
if (r-l<=1)
{
f[r]=p;
return;
}
mid=(l+r)/2;
if (p>f[mid])
work(p,mid+1,r);
else
work(p,l,mid-1);
}

void pai(long l,long r)
{
long i,j,k,mid;
i=l; j=r;
mid=a[(l+r)/2];
do
{
while (a[i]<mid) i=i+1;
while (a[j]>mid) j=j-1;
if (i<=j)
{
k=a[i];a[i]=a[j];a[j]=k;
k=b[i];b[i]=b[j];b[j]=k;
i=i+1; j=j-1;
}
}
while (i<=j);
if (i<r) pai(i,r);
if (l<j) pai(l,j);
}
int main()
{
long i,k;
k=0;
while(scanf("%d",&n)!=EOF)
{
k=k+1;
for (i=1;i<=n;i++)
{
scanf("%d %d",&a[i],&b[i]);
}
pai(1,n);
u=0;
memset(f,0,sizeof(f));
for (i=1;i<=n;i++)
if (b[i]>f[u])
{
u=u+1;
f[u]=b[i];
}
else work(b[i],0,u);

printf("Case %d:\n",k);
if (u<=1)
printf("My king, at most %d road can be built.\n\n",u);
else
printf("My king, at most %d roads can be built.\n\n",u);
}
}

Answer 1

这是我代码，你看看
#include<iostream>
using namespace std;
int ac[500001];
int n;
int temp[500001];
int dp()
{
int i,low,high,mid,len=0;
for(i=1;i<=n;i++)
{
low=1;
high=len;
while(low<=high)
{
mid=(low+high)/2;
if(temp[mid]>=ac[i])
high=mid-1;
else
low=mid+1;
}
temp[low]=ac[i];
if(low>len)len++;
}
return len;
}
int main()
{
int i,a,b,t,len;
t=0;
while(scanf("%d",&n)!=EOF)
{
t++;
for(i=0;i<n;i++)
{
scanf("%d%d",&a,&b);
ac[a]=b;
}
len=dp();
printf("Case %d:\nMy king, at most %d road",t,len);
if(len!=1) printf("s");
printf(" can be built.\n\n");
}
}