PAT A1045 動態規劃
該題目有兩種解法,都是動態規劃中特別經典的解法,一種是最長不下降子序列,一種是最長公共子序列;
第一種方法對於該題目其實有點取巧的感覺;
首先,注意一點,對於最長不下降子序列來說,其序列的元素一定是非遞減的,所以我們的當務之急是如何將值轉換為
遞增序列,從而使得演算法能夠繼續進行;
對於這個問題,我們可以使用hashtable進行處理,也就是利用hashtable重新使得值遞增;
這裡需要注意一下,子序列遞增研究的是不連續的子序列,連續的子序列其實可以用前面的KMP演算法來及進行解決;
對於該問題,首當其中的還是狀態轉移方程。由於該問題還是從0開始研究,所以仍然設定一個一維陣列dp來儲存中間的狀態;
大致思路是限定一個子串序列,然後選擇一個,從第一個開始進行輪詢,這裡有點像插入排序的感覺;
其狀態轉移方程為dp[i]=max(1,dp[j]+1);
該方程可以理解將第i個元素排在j後面,從而繼承j之前的子串序列的長度,1為單個元素的序列長度;
程式碼如下:
#include<iostream> #include<stdio.h> #include<stdlib.h> #include<algorithm> using namespace std; const int maxc=210; const int maxn=10010; int Hashtable[maxc]; int a[maxn],dp[maxn]; int main(){ int n,m,x; scanf("%d%d",&n,&m); memset(Hashtable,-1,sizeof(Hashtable)); for(int i=0;i<m;i++){ scanf("%d",&x); Hashtablet[x]=i; } int L,num=0; scanf("%d",&L); for(int i=0;i<L;i++){ scanf("%d",&x); if(Hashtable[x]>=0){ a[num++]=Hashtable[x]; //進行hashtable的相應轉換 } } int ans=-1; for(int i=0;i<num;i++){ dp[i]=1; for(int j=0;j<i;j++){ if(a[j]<=a[i]&&dp[i]<dp[j]+1){ dp[i]=dp[j]+1; } } ans=max(ans,dp[i]); } printf("%d\n",ans); return 0; }
第二種不太好理解,所以這裡先不再贅述,主要是不能理解為什麼公共部分可以重複輸出;