小明系列問題——小明序列

Time Limit: 3000/1000 MS (Java/Others)????Memory Limit: 65535/32768 K (Java/Others)

Problem Description 大家都知道小明最喜歡研究跟序列有關的問題了，可是也就因為這樣，小明幾乎已經玩遍各種序列問題了。可憐的小明苦苦地在各大網站上尋找著新的序列問題，可是找來找去都是自己早已研究過的序列。小明想既然找不到，那就自己來發明一個新的序列問題吧！小明想啊想，終于想出了一個新的序列問題，他欣喜若狂，因為是自己想出來的，于是將其新序列問題命名為“小明序列”。

　　提起小明序列，他給出的定義是這樣的：
　　①首先定義S為一個有序序列，S={ A1 , A2 , A3 , ... , An }，n為元素個數 ；
　　②然后定義Sub為S中取出的一個子序列，Sub={ Ai1 , Ai2 , Ai3 , ... , Aim }，m為元素個數 ；
　　③其中Sub滿足 Ai1 < Ai2 < Ai3 < ... < Aij-1 < Aij < Aij+1 < ... < Aim ；
　　④同時Sub滿足對于任意相連的兩個Aij-1與Aij都有 ij - ij-1 > d (1 < j <= m， d為給定的整數)；
　　⑤顯然滿足這樣的Sub子序列會有許許多多，而在取出的這些子序列Sub中，元素個數最多的稱為“小明序列”(即m最大的一個Sub子序列)。
　　例如：序列S={2,1,3,4} ，其中d=1；
　　可得“小明序列”的m=2。即Sub={2,3}或者{2,4}或者{1,4}都是“小明序列”。

　　當小明發明了“小明序列”那一刻,情緒非常激動，以至于頭腦凌亂，于是他想請你來幫他算算在給定的S序列以及整數d的情況下，“小明序列”中的元素需要多少個呢？

Input 輸入數據多組，處理到文件結束;
　　輸入的第一行為兩個正整數 n 和 d；(1<=n<=10^5 , 0<=d<=10^5)
　　輸入的第二行為n個整數A1 , A2 , A3 , ... , An，表示S序列的n個元素。(0<=Ai<=10^5)
Output 請對每組數據輸出“小明序列”中的元素需要多少個，每組測試數據輸出一行。
Sample Input 2 0 1 2 5 1 3 4 5 1 2 5 2 3 4 5 1 2
Sample Output 2 2 1解題思路：dp[i]表示第i個數結尾的最大序列，則dp[i] = max{dp[k]} + 1,其中i - k > d；這里可以用線段樹優化，但關鍵是如何滿足i-k>d這個條件。求dp[i]時，我們只把dp[i-d-1]更新至線段樹中，然后在這顆線段樹中找最大的個數#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std;#define lson l,m,rt<<1 #define rson m+1,r,(rt<<1)|1 #define N (int)(1e5+5)int num[4*N],save[N],dp[N];void pushup(int rt) //向上更新 {num[rt]=max(num[rt<<1],num[rt<<1|1]);return ; }void build(int l,int r,int rt) {num[rt]=0;if(l==r)return ;int m=(l+r)>>1;build(lson);build(rson);return ; }void update(int t,int v,int l,int r,int rt) //端點更新 {if(l==r){num[rt]=max(num[rt],v);return ;}int m=(l+r)>>1;if(t<=m)update(t,v,lson);elseupdate(t,v,rson);pushup(rt);}int query(int L,int R,int l,int r,int rt)//找出L,R區間內最大的長度 {if(L<=l&&R>=r)return num[rt];int m=(l+r)>>1;int Max=0;if(L<=m)Max=max(Max,query(L,R,lson));if(R>m)Max=max(Max,query(L,R,rson));return Max; } int main() {int n,d;while(scanf("%d%d",&n,&d)!=EOF){int Max=0;for(int i=1;i<=n;i++){scanf("%d",&save[i]);Max=max(Max,save[i]);}build(0,Max,1);int ans=0;for(int i=1;i<=n;i++){if(i-d-1>=1)update(save[i-d-1],dp[i-d-1],0,Max,1); //這是關鍵，只把i-d-1前面的更新至線段樹中if(save[i]==0)dp[i]=1;elsedp[i]=query(0,save[i]-1,0,Max,1)+1;ans=max(dp[i],ans);}printf("%d\n",ans);}return 0; }

總結

以上是生活随笔為你收集整理的hdu 4521(线段树优化dp)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。