【标题】：PKU-2533(经典的动态规划题)
【关键字】：PKU-2533
【来源】：http://blog.csdn.net/OOspurs/archive/2006/10/01/1315350.aspx

PKU-2533(经典的动态规划题)

如果只输出最长顺序子序列的长度,可以用以下的算法:
设D(i)表示以第i个元素为首元素的顺序子序列最大长度,则
当i=n时,D(n)=1
当i<n时,D(i)=max{D(j)+1} xj>xi且i<j<=n

#include <iostream.h>
#include <stdio.h>

//求最长顺序子序列长度，经典的动态规划思想
int d[1010],data[1010],n;

int lcs(int da[],int n)
{
int i,j,max;

for(i=0;i<n;i++)
  d[i] = 1;
for(i=0;i<n;i++)
{
  for(j=0;j<i;j++)
  {
   //序列要包含data[i]的
   if(data[i]>data[j])
   {
    if(d[i]<d[j]+1)
     d[i] = d[j] + 1;
   }
  }
}
max = 0;
for(i=0;i<n;i++)
{
  if(max<d[i])
   max = d[i];
}
return max;
}

int main()
{
int i;
//freopen("1.txt","r",stdin);

    cin>>n;

  for(i=0;i<=n;i++)
  {
   cin>>data[i];
  }
  cout<<lcs(data,n)<<endl;

return 0;
}

在VC里调试标准C语言：【上一篇】
在QT4中使用QTableView制作属性编辑器：【下一篇】

【相关文章】
没有相关文章

【随机文章】

C++ 标准模板库（STL）编程示例 - 容器适配器Stack

简单指令型计算器（1）指令系统和汇编编译器〈下〉

Microsoft Internal Coding Guidelines / Design Guidelines for Managed code

基于CMPP2及东软API短信平台的开

date 的用法

Photoshop创意壁纸教程

Apache2.0.47和Tomcat4.1.27整合

3DS Max 7.0 PF Source粒子全攻略（34）

linux相关的资源[不断更新]

我的WEB服务器搭建之经验 (轉自cu)

【相关评论】

没有相关评论

【发表评论】