902
【北大夏令營筆記-動態規劃】百練2757-最長上升子序列
2757:最長上升子序列總時間限製: 2000ms 內存限製: 65536kB
描述
一個數的序列bi，當b1 < b2 < ... < bS的時候，我們稱這個序列是上升的。對於給定的一個序列(a1, a2, ..., aN)，我們可以得到一些上升的子序列(ai1, ai2, ..., aiK)，這裏1 <= i1 < i2 < ... < iK <= N。比如，對於序列(1, 7, 3, 5, 9, 4, 8)，有它的一些上升子序列，如(1, 7), (3, 4, 8)等等。這些子序列中最長的長度是4，比如子序列(1, 3, 5, 8).
你的任務，就是對於給定的序列，求出最長上升子序列的長度。
輸入
輸入的第一行是序列的長度N (1 <= N <= 1000)。第二行給出序列中的N個整數，這些整數的取值範圍都在0到10000。
輸出
最長上升子序列的長度。
樣例輸入
7
1 7 3 5 9 4 8
樣例輸出
4
來源
翻譯自 Northeastern Europe 2002, Far-Eastern Subregion 的比賽試題
//動態規劃
AC代碼：
（以後要學會用純c++）
//以ak為終點的最長上升子序列的長度
//“人人為我”遞推型動歸
/*
maxLen(k)表示以ak作為“終點”的最長上升子序列的長度。
maxLen(k)的值，就是ak左邊，“終點”數值小於ak，且長度最大的那個上
升子序列的長度再加1。因為ak左邊任何“終點”小於ak的子序列，加上ak
後就能形成一個更長的上升子序列
*/
#include<stdio.h>
#include<algorithm>
//max()、*max_element()函數均在algorithm頭文件裏
using namespace std;
const int MAX=1010;
int a[MAX];
int maxLen[MAX];
int main()
{
int i,j,n,m;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d",&a[i]);
maxLen[i]=1;
}
for(i=2;i<=n;i++)
for(j=1;j<i;j++)
if(a[i]>a[j])
maxLen[i]=max(maxLen[i],maxLen[j]+1);
printf("%d\n",*max_element(maxLen+1,maxLen+n+1));
return 0;
}
//“我為人人”遞推型動歸
#include<stdio.h>
#include<algorithm>
using namespace std;
const int MAX=1010;
int a[MAX];
int maxLen[MAX];
int main()
{
int i,j,n,m;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d",&a[i]);
maxLen[i]=1;
}
for(i=1;i<=n;i++)
for(j=i+1;j<=n;j++)
if(a[i]<a[j])
maxLen[j]=max(maxLen[j],maxLen[i]+1);
printf("%d\n",*max_element(maxLen+1,maxLen+n+1));
return 0;
}
最後更新：2017-04-03 05:39:27