50分求助

Doufu_killer @ 2024-01-28 11:28:17

#include <bits/stdc++.h>
using namespace std;
#define ull unsigned long long
#define INF 1001
ull n;
ull dp[INF][INF] = {0};
ull in1[INF] = {0};
ull in2[INF] = {0};
void in()
{
  cin >> n;
  for (ull i = 1; i <= n; i++)
    cin >> in1[i];
  for (ull i = 1; i <= n; i++)
    cin >> in2[i];
}
ull LCS()
{
  for (ull i = 1; i <= n; i++)
  {
    for (ull j = 1; j <= n; j++)
    {
      dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
      if (in1[i] == in2[j])
        dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1);
    }
  }
  return dp[n][n];
}
int main()
{
  in();
  ull a = LCS();
  cout << a << endl;
  return 0;
}

by dysyzxhzh @ 2024-01-28 11:51:57

1.你的数组开小了，RE

2.开大之后会MLE

by Doufu_killer @ 2024-01-28 11:58:03

@dysyzxhzh so?

by dysyzxhzh @ 2024-01-28 12:01:16

我有点懵QWQ

我可以让它不RE

但MLE了o(TヘTo)

#include <bits/stdc++.h>
using namespace std;
#define INF 10010
long long n;
long long dp[INF][INF];
long long in1[INF];
long long in2[INF];
void in() {
    cin >> n;
    for (long long i = 1; i <= n; i++)
        cin >> in1[i];
    for (long long i = 1; i <= n; i++)
        cin >> in2[i];
}
long long LCS() {
    for (long long i = 1; i <= n; i++) {
        for (long long j = 1; j <= n; j++) {
            dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
            if (in1[i] == in2[j])
                dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1);
        }
    }
    return dp[n][n];
}
int main() {
    in();
    cout << LCS() << endl;
    return 0;
}

by Doufu_killer @ 2024-01-28 12:02:55

@dysyzxhzh OMG,那我再看看

by Bingxiu @ 2024-01-28 12:25:05

@Doufu_killer @dysyzxhzh 要 O(n\log n)，如果两个排列分别是置换 P,Q，则 LCS(P,Q)=LCS(P \times W,Q \times W)（其中 W 也是一个置换），所以取 W=P^{-1}，得到 LCS(P,Q)=LCS(PP^{-1},QP^{-1})=LCS(E,QP^{-1})=LIS(QP^{-1})

by Doufu_killer @ 2024-01-28 15:04:28

@Bingxiu ???

by Bingxiu @ 2024-01-28 15:11:11

@Doufu_killer 因为题目是两个排列，所以排列可以对应到置换，然后用置换的一些性质做，说人话就是排列同时交换同样数值，LCS 大小不变，比如 (1,2,3,4,5),(2,3,1,5,4) 的 LCS 长度和 (1,\red4,3,\red2,5),(\red4,3,1,5,\red2) 的 LCS 长度相等

by Doufu_killer @ 2024-01-28 15:15:24

@Bingxiu （突然明悟）感谢！