.
.
.
.
.

分析

定義f[i]表示以位置i為結(jié)尾的LIS長(zhǎng)度。邊界條件為f[0]=1，狀態(tài)轉(zhuǎn)移方程為

f[i]=max(f[i],f[j]+1)(j=1…i-1 a[i]>=a[j])

我們觀察到，f[i]的值由前面的數(shù)字推得，所以我們只要從前往后轉(zhuǎn)移，就可以保證每次使用的數(shù)字都是已經(jīng)確定的值。

考慮兩個(gè)數(shù)a[x]和a[y]，若x< y且f[x]==f[y]，那么在轉(zhuǎn)移的過(guò)程中，選擇a[x]更有潛力，可以獲得最優(yōu)的值，所以當(dāng)f數(shù)組的值一樣時(shí)，應(yīng)選擇最小的數(shù)。

按照f(shuō)[i]==k分類，記錄f[i]==k的所有i的最小值，f有兩個(gè)特點(diǎn)：

(1)f[i]在計(jì)算過(guò)程中單調(diào)不升

(2)f數(shù)組是有序的，f[i]<=f[i+1]

根據(jù)這些性質(zhì)，可以方便地求解：

(1)設(shè)當(dāng)前求出的LIS長(zhǎng)度為ans（初始值為1），當(dāng)前元素為a[x]

(2)如果a[x]>f[ans]，直接加入f數(shù)組的末尾，且ans++；否則在f數(shù)組中二分查找，找到第一個(gè)比a[x]小的數(shù)字f[k]，f[k+1]=a[x]，這樣做保證a[x]<=f[k+1]（根據(jù)性質(zhì)1，2）

(3)最后的ans即為答案
.
.
.
.
.

程序：

#include<iostream> using namespace std; int a[100000],f[100000],n,ans,tj;int work(int w,int l,int r) {while (l<r){int mid=(l+r)/2;if (w>=f[mid]) l=mid+1;else r=mid;}return l; }int main() {cin>>n;for (int i=0;i<n;i++)cin>>a[i];f[1]=a[0]; for (int i=1;i<n;i++){if (f[ans]<a[i]) tj=++ans;else tj=work(a[i],1,ans+1);f[tj]=a[i];}cout<<n-ans;return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/YYC-0304/p/9499908.html

總結(jié)

以上是生活随笔為你收集整理的洛谷P3902 递增的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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