基地A_I @ 2019-03-12 21:10:57
求大佬教 LCS 满分算法!!!
我的代码:
#include<bits/stdc++.h>
#define maxn 1007
using namespace std;
int n,x[maxn],y[maxn];
int dp[maxn][maxn];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i)
scanf("%d",&x[i]);
for(int i=1;i<=n;++i)
scanf("%d",&y[i]);
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
{
if(x[i] == y[j]) dp[i][j] = dp[i-1][j-1]+1;
else dp[i][j] = max(dp[i][j-1] ,dp[i-1][j]);
}
printf("%d",dp[n][n]);
return 0;
}
by Catalan1906 @ 2019-03-12 21:12:49
@基地A_I 二分优化,你这样做显然是AC不了的
by 基地A_I @ 2019-03-12 21:21:40
@Neptune_Disaster 求大佬教二分优化!
by Catalan1906 @ 2019-03-12 21:22:50
@基地A_I 其实也可以用树状数组优化……还有你数组开这么小明显是过不了的……