前幾天看了關于動態規劃的內容，基本上講的都是最大不下降序列，所以第一次博客 就寫這個東西了。
給出一系列的數，給出一個整數，即最長不下降子序列（code vs 1567)
先另創一個數組，用來記錄某一個數到目前為止的最大長度，用for語句將所有元素遍歷 一遍就可以確定最長不下降子序列的長度了。 比如給出：21 22 63 15 從63開始（15不需要，其本身長度即為1），沒有元素比他大，故它的長度還是1，然后 是22，后面有一個元素比它大，所以其長度為1+1（本身長度）=2，對于21尋找比它大的且長度 最大的元素，即22（長度為2），故該元素長度為3。此時遍歷完畢，最大值為3。
下面上代碼：
#include<iostream>#include<stdio.h>using namespace std;int a[5000],dp[5000];int main(void){ int n,len=1; cin>>n; for(int i=1;i<=n;i++) { cin>>a[i]; dp[i]=1; } for(int i=2;i<=n;i++) //其實從前從后遍歷都一樣 { for(int j=1;j<i;j++) { if(a[i]>a[j]) { dp[i]=max(dp[j]+1,dp[i]); } } len=max(len,dp[i]); } cout<<len<<endl;}另解 可以另開一個堆棧數組stack[]，每次取棧頂的元素stack[top]和讀到的元素temp 比較，如果temp>top，則將temp壓入棧頂，如果temp
#include<iostream>#include<stdio.h>#include<cstdlib>using namespace std;int main(void){int i,j,n,top,temp;int stack[1001];cin>>n;top=0;stack[0]=-1;for(i=0;i<n;i++){ cin>>temp; if(temp>stack[top]) { stack[top++]=temp; } else { int low=1,high=top; int mid; while(low<high) { mid=(low+high)/2; if(temp>stack[mid]) { low=mid+1; } else { high=mid-1; } } stack[mid]=temp; }}cout<<top<<endl; //話說我寫代碼都不喜歡寫return的。。。}關于這個最長不下降子序列有一道題:攔截導彈(NOip1999) 題解： 這題第一問其實就是最長不上升子序列問題，之前有講，然后第二問其實就是問有 幾個最長不上升子序列，這個要用一個定理，書上寫的是：即一個序列中不上升 子序列的最小覆蓋數等于序列中最長上升序列的長度。（這什么鬼話，表示并沒有 看懂）其實說白了就是該問可以轉化為求最長不下降子序列的長度（至于為什么 ，因為前面那個沒有看懂的定理，反正用就好咯） 下面是代碼：
#include<iostream>#include<stdio.h>#include<cstdlib>#include<string.h>using namespace std;int dp[5000],a[5000];int main(void){int i,j,n=1,len=0,count=0;while(scanf("%d",&a[n])!=EOF) n++;for(i=1;i<n;i++){ dp[i]=1; for(j=1;j<=i;j++) { if(a[i]<a[j]&&dp[i]<dp[j]+1) dp[i]=dp[j]+1; if(dp[i]>len) len=dp[i]; }}memset(dp,0,sizeof(dp));for(i=1;i<=n;i++){ dp[i]=1; for(j=1;j<=i;j++) { if(a[i]>a[j]&&dp[i]<dp[j]+1) dp[i]=dp[j]+1; if(count<dp[i]) count=dp[i]; }}cout<<len<<'/n'<<count<<endl;}新聞熱點
疑難解答
