leetcode

0 class Solution {

1 int dp[2001][2001][2];

2

3 void norm(vector<int> &arr) {

4 sort(arr.begin(), arr.end());

5 int i = 1, j = 1;

6 while (i < arr.size()) {

7 if (arr[i] != arr[i - 1]) arr[j++] = arr[i];

8 i++;

9 }

10 arr.resize(j);

11 }

12

13 int rec(const vector<int> &arr1, const vector<int> &arr2, int i, int j, bool other) {

14 if (i >= arr1.size()) return 0;

15 int prev = !other ? i == 0 ? INT_MIN : arr1[i - 1] : arr2[j];

16 j = upper_bound(arr2.begin() + j, arr2.end(), prev) - arr2.begin();

17 if (dp[i][j][other]) return dp[i][j][other];

18

19 int res = 2002;

20 if (j < arr2.size()) res = rec(arr1, arr2, i + 1, j, true) + 1;

21 if (prev < arr1[i]) res = min(res, rec(arr1, arr2, i + 1, j, false));

22 return dp[i][j][other] = res;

23 }

24

25 public:

26 int makeArrayIncreasing(vector<int> &arr1, vector<int> &arr2) {

27 norm(arr2);

28 int res = rec(arr1, arr2, 0, 0, false);

29 return res >= 2002 ? -1 : res;

30 }

31 };