O(n^2)代码:
#include<iostream>
using namespace std;
int h[40000],d[40000];
int main()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
int test=0;
while(1)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
int i,j,k;
test++;
scanf("%d",&h[1]);
if(h[1]==-1) break;
k=1;
while(scanf("%d",&j)!=EOF&&j!=-1)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
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;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
O(nlogn)代码:
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
/**//*============================*\
最长下降子序列 O(nlogn)
\*============================*/
#include<iostream>
using namespace std;
const int inf=1000000;
int a[30000],b[30000];//b[i]表示长度为i的下降序列中,末尾数最大的那个序列的代表。
int n;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int lds()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
int ans=0;
b[0]=inf;
for(int i=1;i<=n;i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
int l=1,r=ans;
while(l<=r) //找l最小的b[l],使b[l]<=a[i].
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
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;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int main()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
int test=0;
while(scanf("%d",&a[1])!=EOF&&a[1]!=-1)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
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;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
posted on 2010-09-06 20:05
wuxu 阅读(381)
评论(0) 编辑 收藏 引用 所属分类:
动态规划