`
kmplayer
  • 浏览: 508877 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

国际大学生程序设计竞赛例题_3.2导弹(最长上升子序列)

J# 
阅读更多
1.题意:求一个序列的最长子序列.
要求:1>2<3>4<5...
2.解决:动态规划.
如果d[j]为奇数,并且h[i]<h[j],并且d[j]+1>d[i]
d[i]=d[j]+1;
如果d[j]为偶数,并且h[i]>h[j],并且d[j]+1>d[i]
d[i]=d[j]+1;
特殊性:从第1个开始,依次向前回溯.
3.实现代码:
#include <iostream>
using namespace std;

const int MAXN=1010;
int h[MAXN]; //导弹高度
int d[MAXN]; //每个元素作为结尾的最长个数
int ans;//保存结果

int main()
{
    freopen("3.2.in","r",stdin);
    int n;
    while(cin>>n,n)
    {
        for(int i=0;i<n;i++)
            cin>>h[i];
        ans=1;
        memset(d,0,sizeof(d));

        for(int i=0;i<n;i++)
        {
            d[i]=1;
            for(int j=i-1;j>=0;j--)
            {
                if( (d[j]&1)&&h[i]<h[j]&&d[j]+1>d[i] )
                    d[i]=d[j]+1;
                if( !(d[j]&1)&&h[i]>h[j]&&d[j]+1>d[i] )
                    d[i]=d[j]+1;
            }
            if(ans<d[i]) ans=d[i];
        }
        cout<<ans<<endl;
    }
    return 0;
}
  • 3.2.rar (11.1 KB)
  • 下载次数: 0
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics