-
前面
參考部落格：Dilworth定理 Dilworth定理是個啥東東
的代碼：P1020 飛彈攔截 能過50%
對于STL中 二分查找的函數，自定義cmp：題解 P1020 【飛彈攔截】
對于LIS的
寫法：O(NlogN)做法：貪心+二分
沒想到，本來以為是個簡單的DP，咋整來這麼多知識？？
-
題目描述
題目就是
①先求最長的，非上升的，子序列的長度
②求這樣的子序列 有幾個，根據那什麼定理，就是求出來最長的，上升的子序列長度。
這個什麼定理：偏序集能劃分成的最少的全序集個數等于最大反鍊的元素個數。
偏序關系是 >=，全序集的個數（最長的非上升子序列的個數）== 最大反鍊（最長的上升子序列）的長度
-
兩種方法
最長的非上升子序列長度，最長的上升子序列長度，是同樣的思路。
的思想是動态規劃。
的思想是 貪心+二分。
-
動态規劃
動态規劃的思想，簡單說來。
// 50 %
//P1020
const int maxn=1e5+5;
int num[maxn];
int dp[maxn];
int main()
{
int ii=1;
while(scanf("%d",&num[ii])!=EOF)
ii++;
ii--;
int len=ii;
for(int i=1;i<=len;i++)
dp[i]=1;
for(int i=2;i<=len;i++)
{
for(int j=1;j<i;j++)
{
if(num[j]>=num[i])
dp[i]=max(dp[i],dp[j]+1);
}
}
int ans1=0;
for(int i=1;i<=len;i++)
{
// cout<<dp[i]<<" ";
ans1=max(ans1,dp[i]);
}
cout<<ans1<<endl;
for(int i=1;i<=len;i++)
dp[i]=1;
for(int i=2;i<=len;i++)
{
for(int j=1;j<i;j++)
{
if(num[j]<num[i])
dp[i]=max(dp[i],dp[j]+1);
}
}
int ans2=0;
for(int i=1;i<=len;i++)
{
// cout<<dp[i]<<" ";
ans2=max(ans2,dp[i]);
}
cout<<ans2<<endl;
}
以非上升序列為例：
數組表示 以第
個元素作為結尾，最長的非上升序列的長度。
是以，初始化全部為1。
遞推關系式為：
。
說明 包含第
個元素的長度，是由前面的，某個長度推來的。（滿足條件emmm），大概這個意思。
最後要注意的是，需要循環周遊
數組，找到最大值。這是因為
的定義，但是最長的長度并不一定包含了最後一個元素，并不一定是
.
-
貪心+二分
表示表示長度為
的LIS結尾元素的最小值。
利用貪心的思想，對于一個上升子序列，顯然目前最後一個元素越小，越有利于添加新的元素，這樣LIS長度自然更長。
就是這個部落格，講的肥腸好
如果你不想寫二分的代碼，你可以使用自帶的STL函數。但是由于upper_bound函數，要求是遞增序列，我們在求最長的非上升子序列長度時，dp數組的必然是非遞增序列，是以需要重新定義函數，
這裡的greater<int>()就是c++友情提供的友善的大于函數，這樣就不用自己動手寫一個cmp函數了(霧).
const int maxn=1e5+5;
int num[maxn];
int dp[maxn];
int main()
{
int ii=1;
while(scanf("%d",&num[ii])!=EOF)
ii++;
ii--;
int len=ii;
int pos=1;
dp[1]=num[1];
for(int i=2;i<=len;i++)
{
if(num[i]<=dp[pos])
{
dp[++pos]=num[i];
}
else
dp[upper_bound(dp+1,dp+pos+2,num[i],greater<int>() )-dp]=num[i];
}
cout<<pos<<endl;
//最長上升子序列
for(int i=1;i<=len;i++)
dp[i]=9999999;
pos=0;
dp[1]=num[1];
for(int i=2;i<=len;i++)
{
if(num[i]>dp[pos])
{
dp[++pos]=num[i];
}
else
dp[lower_bound(dp+1,dp+pos+2,num[i])-dp]=num[i];
}
cout<<pos<<endl;
}