1045Favorite Color Stripe （DP)

1045 Favorite Color Stripe （DP)

思路：1.$dp$。

令$dp[i][j]$表示以$b[i]$为最后一个匹配颜色对于前$j$个数的最大长度。

$dp[i][j]=max(dp[i-1][j],dp[i][j-1])$

$if(a[i]==b[j])$ $dp[i][j]++$

时间复杂度：$O(nm)$

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=205,M=1e4+5,inf=0x3f3f3f3f,mod=1e9+7; #define mst(a,b) memset(a,b,sizeof a) #define lx x<<1 #define rx x<<1|1 #define reg register #define PII pair<int,int> #define fi first #define se second #define pb push_back #define il inline int tot,n,m,a[M],b[N],dp[N][M],x; int main(){ scanf("%d",&tot); scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&b[i]); } scanf("%d",&m); for(int i=1;i<=m;i++) scanf("%d",&a[i]); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ dp[i][j]=max(dp[i][j-1],dp[i-1][j]); if(a[j]==b[i]) dp[i][j]++; } } printf("%d\n",dp[n][m]); return 0; }

2.转换为$LIS$。

因为喜欢的颜色不同，可以用下标映射为递增序列。

然后找最长非递减序列即可。

时间复杂度：$O(mlogm)$

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=205,M=1e4+5,inf=0x3f3f3f3f,mod=1e9+7; #define mst(a,b) memset(a,b,sizeof a) #define lx x<<1 #define rx x<<1|1 #define reg register #define PII pair<int,int> #define fi first #define se second #define pb push_back #define il inline int tot,n,m,pos[N],a[M],dp[M],cnt; int main(){ scanf("%d%d",&tot,&n); for(int i=1,x;i<=n;i++){ scanf("%d",&x);pos[x]=i; } scanf("%d",&m);n=0; for(int i=1,x;i<=m;i++){ scanf("%d",&x); if(pos[x]) a[++n]=pos[x]; } for(int i=1;i<=n;i++){ if(!cnt||dp[cnt]<=a[i]) dp[++cnt]=a[i]; else { int p=upper_bound(dp+1,dp+cnt+1,a[i])-dp; dp[p]=a[i]; } } printf("%d\n",cnt); return 0; }