1281：最長上升子序列

時間限制: 1000 ms ??? ??? 內(nèi)存限制: 65536 KB
提交數(shù): 15871 ??? 通過數(shù): 8180

【題目描述】

一個數(shù)的序列bibi，當b1<b2<...<bSb1<b2<...<bS的時候，我們稱這個序列是上升的。對于給定的一個序列(a1,a2,...,aN)(a1,a2,...,aN)，我們可以得到一些上升的子序列(ai1,ai2,...,aiK)(ai1,ai2,...,aiK)，這里1≤i1<i2<...<iK≤N1≤i1<i2<...<iK≤N。比如，對于序列(1,7,3,5,9,4,8)，有它的一些上升子序列，如(1,7),(3,4,8)等等。這些子序列中最長的長度是4，比如子序列(1,3,5,8)。

你的任務(wù)，就是對于給定的序列，求出最長上升子序列的長度。

【輸入】

輸入的第一行是序列的長度N(1≤N≤1000)。第二行給出序列中的N個整數(shù)，這些整數(shù)的取值范圍都在0到10000。

【輸出】

最長上升子序列的長度。

【輸入樣例】

7 1 7 3 5 9 4 8

【輸出樣例】

4

【分析】

算法思想：請見

https://www.bilibili.com/video/BV1ni4y1u7uX?from=search&seid=2791451597285109637&spm_id_from=333.337.0.0

設(shè)f[i]表示以a[i]結(jié)尾的最長上升子序列。

（1）階段：子序列結(jié)尾的位置，即 i 。

（2）狀態(tài)：j=1...i，f[j]序列中的每個值都是狀態(tài)。

（3）決策：a[i]是否加到序列中？

（4）策略：最大化上升子序列長度。

（5）狀態(tài)轉(zhuǎn)移方程：

（6）邊界：f[1...n]=1

（7）目標：max(f[i])

#include <stdio.h> #define MAXN 1010 int a[MAXN],f[MAXN]; //f[i]表示以a[i]為結(jié)尾的最長上升子序列的長度 int max(int x,int y) {return x > y ? x : y; } int main() {int n;int i,j,ans=1;scanf("%d",&n);for(i=1;i<=n;i++){scanf("%d",&a[i]);f[i]=1; // 初始化f[i]}// 動態(tài)更新f[i]for(i=2;i<=n;i++){for(j=1;j<i;j++){if(a[i]>a[j])f[i]=max(f[i],f[j]+1);}ans=max(ans,f[i]);}printf("%d\n",ans);return 0; }

信息學奧賽一本通（C++版）在線評測系統(tǒng)

總結(jié)

以上是生活随笔為你收集整理的信息学奥赛一本通（1281：最长上升子序列）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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