随笔-68  评论-10  文章-0  trackbacks-0
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]==-1break;
        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 阅读(399) 评论(0)  编辑 收藏 引用 所属分类: 动态规划

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理