【CF10D】LCIS(LCIS)

题意:求两个序列的LCIS

n,m<=300,a[i]<=1e9

题意:O(n^2)

O(n^3)的话设dp[i,j]为A终点为a【1..i】且B终点为b[j]的最大长度,分a[i]==b[j]和a[i]!=b[j]转移,枚举前一个在b中取的位置k转移

发现转移的下标集合每次只扩大最后一个,用前缀max保存

 #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int,int> PII;
typedef pair<ll,ll> Pll;
typedef vector<int> VI;
typedef vector<PII> VII;
typedef pair<ll,ll>P;
#define N 510
#define M 1000000
#define INF 1e9
#define fi first
#define se second
#define MP make_pair
#define pb push_back
#define pi acos(-1)
#define mem(a,b) memset(a,b,sizeof(a))
#define rep(i,a,b) for(int i=(int)a;i<=(int)b;i++)
#define per(i,a,b) for(int i=(int)a;i>=(int)b;i--)
#define lowbit(x) x&(-x)
#define Rand (rand()*(1<<16)+rand())
#define id(x) ((x)<=B?(x):m-n/(x)+1)
#define ls p<<1
#define rs p<<1|1
#define fors(i) for(auto i:e[x]) if(i!=p) const int MOD=1e9+,inv2=(MOD+)/;
double eps=1e-;
int dx[]={-,,,};
int dy[]={,,-,}; int dp[N][N],pre[N][N],a[N],b[N],c[N]; int read()
{
int v=,f=;
char c=getchar();
while(c<||<c) {if(c=='-') f=-; c=getchar();}
while(<=c&&c<=) v=(v<<)+v+v+c-,c=getchar();
return v*f;
} int main()
{
int n=read();
rep(i,,n) a[i]=read();
int m=read();
rep(i,,m) b[i]=read();
rep(i,,n)
{
int mx=,y=;
rep(j,,m)
{
dp[i][j]=pre[i][j]=;
if(a[i]!=b[j])
{
dp[i][j]=dp[i-][j];
pre[i][j]=j;
}
if(a[i]>b[j]&&mx<dp[i-][j])
{
mx=dp[i-][j];
y=j;
}
if(a[i]==b[j])
{
dp[i][j]=mx+;
pre[i][j]=y;
}
}
}
int x=n,y,ans=;
rep(i,,m)
if(dp[n][i]>ans)
{
ans=dp[n][i];
y=i;
}
printf("%d\n",ans);
if(ans==) return ;
int t=;
while(x)
{
if(a[x]==b[y]) c[++t]=b[y];
y=pre[x][y];
x--;
}
per(i,ans,) printf("%d ",c[i]);
return ;
}
上一篇:「CF10D」LCIS


下一篇:【二维树状数组】【CF10D】 LCIS