肥婆纳妾 @ 2018-10-30 15:19:59
#include<bits/stdc++.h>
using namespace std;
int dp[2][100005],a[100005],b[100005];
int main()
{
int n;
cin >> n;
for (int i = 1; i <= n;cin>>a[i++]);
for (int j = 1; j <= n; cin >> b[j++]);
for(int i=1;i<=n;++i)
for (int j = 1; j <= n; ++j)
if (a[i] == b[j])
dp[i%2][j] = dp[i%2==0?1:0][j - 1] + 1;
else
dp[i%2][j] = max(dp[i % 2 == 0 ? 1 : 0][j], dp[i % 2][j - 1]);
cout << dp[n%2][n];
return 0;
}
by RiverFun @ 2018-10-30 15:21:46
@肥婆纳妾
by ArachnidaKing @ 2018-10-30 15:22:42
那就优化时间啊!
by Yae_Sakura @ 2018-10-30 15:23:10
用dp是O(n^2)过不了,这题要用二分+贪心的算法求
by 肥婆纳妾 @ 2018-10-30 15:26:21
@远藤沙椰 二分答案吗?
by Yae_Sakura @ 2018-10-30 15:28:28
不,是用二分查找优化贪心算法