O(n^2)代码：
#include<iostream>
using namespace std;
int h[40000],d[40000];
int main()
{
int test=0;
while(1)
{
int i,j,k;
test++;
scanf("%d",&h[1]);
if(h[1]==-1) break;
k=1;
while(scanf("%d",&j)!=EOF&&j!=-1)
{
h[++k]=j;
}
h[0]=40000;
memset(d,0,sizeof(d));
for(i=1;i<=k;i++)
for(j=0;j<i;j++)
if(h[j]>h[i]&&d[j]+1>d[i])
d[i]=d[j]+1;
int ans=0;
for(i=1;i<=k;i++)
if(d[i]>ans) ans=d[i];
if(test!=1) printf("\n");
printf("Test #%d:\n",test);
printf(" maximum possible interceptions: %d\n",ans);
}
//system("pause");
return 0;
}
O(nlogn)代码：
/**//*============================*\
最长下降子序列 O(nlogn)
\*============================*/
#include<iostream>
using namespace std;
const int inf=1000000;
int a[30000],b[30000];//b[i]表示长度为i的下降序列中，末尾数最大的那个序列的代表。
int n;
int lds()
{
int ans=0;
b[0]=inf;
for(int i=1;i<=n;i++)
{
int l=1,r=ans;
while(l<=r) //找l最小的b[l],使b[l]<=a[i].
{
int t=(l+r)/2;
if(b[t]>a[i]) l=t+1;
else r=t-1;
}
b[l]=a[i];
if(l>ans) ans++;
}
return ans;
}
int main()
{
int test=0;
while(scanf("%d",&a[1])!=EOF&&a[1]!=-1)
{
int i,t;
n=1;
test++;
while(scanf("%d",&t)!=EOF&&t!=-1)
a[++n]=t;
if(test!=1) printf("\n");
printf("Test #%d:\n",test);
printf(" maximum possible interceptions: %d\n",lds());
}
//system("pause");
return 0;
}
posted on 2010-09-06 20:05
wuxu 阅读(398)
评论(0) 编辑 收藏 引用 所属分类:
动态规划