把序列M處理為有序序列，并且M不存在的序列要在A中刪除。

對A進行了處理之后，執(zhí)行LIS的操作（O(N^2)復(fù)雜度）。當然可以優(yōu)化為對數(shù)復(fù)雜度的，不過pat不卡這個。

LCS解法：動態(tài)規(guī)劃 | 保留重復(fù)元素的LCS 1045

AC代碼：

#include <stdio.h> #include <memory.h> #include <math.h> #include <string> #include <vector> #include <set> #include <stack> #include <queue> #include <algorithm> #include <map>#define I scanf #define OL puts #define O printf #define F(a,b,c) for(a=b;a<c;a++) #define FF(a,b) for(a=0;a<b;a++) #define FG(a,b) for(a=b-1;a>=0;a--) #define LEN 10010 #define MAX (1<<30)-1 #define V vector<int>using namespace std;int hashTable[210]; //將輸入顏色映射為遞增序列 int A[10010]; //處理后的顏色序列（用LIS對這個數(shù)組進行求解 int dp[10010]; //dp[i]記錄 0 ~ i 最多的遞增序列個數(shù) int main(){ // freopen("1045.txt","r",stdin);int i,N,M,L,x,j;memset(hashTable,-1,sizeof hashTable);I("%d",&N);I("%d",&M);FF(i,M){I("%d",&x);hashTable[x]=i;}I("%d",&L);int num=0; //處理后A數(shù)組顏色的總和 FF(i,L){I("%d",&x);if(hashTable[x]>=0){A[num++]=hashTable[x];}}int ans=0;FF(i,num){dp[i]=1;FF(j,i){if(A[j]<=A[i]){dp[i]=max(dp[i],dp[j]+1);}}ans=max(ans,dp[i]);}O("%d\n",ans);return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/TQCAI/p/8571481.html

總結(jié)

以上是生活随笔為你收集整理的动态规划 | 对输入进行hash处理的LIS 1045的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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