題目：

長度為n的序列a1, a2, ..., an,選出滿足 j < i 時(shí), a[j] < a[i] 最長子序列

分析：

當(dāng)選擇第i個(gè)時(shí)候，在j

狀態(tài)：dp[i]表示以i為終點(diǎn)的最大上升序列

轉(zhuǎn)移方程：dp[i]?=?max{dp[j]?|?j

核心：for(i?=?1;?i<=n;?i++)

{

dp[i]?=?1;

for(j?=?1;?j

{

if(a[i]>a[j])

dp[i]?=?max(dp[i],?dp[j]?+?1);

}

}

代碼：#include?

#include?

#include?

#include?

#include?

#include?

#include?

#include?

#include?

#include?

#include?

using?namespace?std;

int?v[10000+10];

int?dp[10000+10];

int?main()

{

//freopen("a.txt",?"r",?stdin);

int?n,?i,?j,?ans;

while(~scanf("%d",?&n)?&&?n)

{

for(i?=?1;?i<=n;?i++)

{

scanf("%d",?&v[i]);

}

ans?=?0;

memset(dp,?0,?sizeof(dp));

for(i?=?1;?i<=n;?i++)

{

dp[i]?=?1;

for(j?=?i-1;?j>=1;?j--)

{

if(v[i]?>?v[j])

dp[i]?=?max(dp[i],?dp[j]?+?1);

}

ans?=?max(ans,?dp[i]);

}

printf("%d\n",?ans);

}

return?0;

}

二分優(yōu)化：

如果子序列長度相同，則終點(diǎn)越小，則后面增長的潛能就越大

所以，將長度相同的位置設(shè)成其中最小值

狀態(tài)：dp[i]表示長度為i的序列中終點(diǎn)最小的值

轉(zhuǎn)移：因?yàn)閐p[i]單調(diào)遞增，若a[j]>dp[i],則加入其后，若a[j]

優(yōu)化代碼：#include?

#include?

#include?

#include?

#include?

#include?

#include?

#include?

#include?

#include?

using?namespace?std;

#define?INF?0x7f7f7f7f

#define?MAX?1000+10

int?a[MAX];

int?dp[MAX];

int?main()

{

freopen("a.txt",?"r",?stdin);

int?n,?i,?j;

while(~scanf("%d",?&n)?&&?n)

{

fill(dp,?dp+n,?INF);

for(i?=?1;?i<=n;?i++)

{

scanf("%d",?&a[i]);

}

for(i?=?1;?i<=n;?i++)

{

*lower_bound(dp,?dp+n,?a[i])?=?a[i];

}

printf("%d\n",?lower_bound(dp,?dp+n,?INF)?-?dp);

}

return?0;

}

PS(有序二分搜索)：

1、lower_bound(first, last, value);返回一個(gè)指針，指向ai>= value的第一個(gè)元素。

2、upper_bound(first, last, value);返回一個(gè)指針，指向ai>?value的第一個(gè)元素。

總結(jié)

以上是生活随笔為你收集整理的优化 最长上升子序列_LIS - 最长上升子序列 （二分优化）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。