dp解的题,空间优化了 ,t了五组数据 ,该如何优化呢?

P1439 【模板】最长公共子序列

肥婆纳妾 @ 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

不,是用二分查找优化贪心算法


|