题目描述：
给出两个数组 $arr1,arr2$ ，返回使得 $arr1$ 严格递增所需要的最小的操作次数。
每步操作可以在两个数组中分别选取下标 $i,j$ ，然后 $arr1[i] = arr2[j]$ 。
如果无法让 $arr1$ 严格递增，返回 $-1$ .
数据范围：
$1\le n,m \le 2000;0\le num \le 10^9$
题解：
首先 $arr2$ 中的每个数只能使用一次，因为严格递增。所以可以对 $arr2$ 排序降重。并且替换次数有限制，最大为 $min(n, m)$ ， $[0, \min(n,m)]$ 。
二维最长公共子序列模型
类似最长公共子序列，可以使用 $dp[i][j]$ 表示 $arr1$ 前 $i$ 个字符，替换了 $j$ 次能够得到的最小的末尾数字。那么当前第 $i$ 位，如果 $arr1[i] > dp[i - 1][j]$ ，则可以不替换，直接接上；替换的话需要找 $dp[i-1][j-1]$ ，因为当前替换的话消耗了一次替换次数，所以需要向前找 $j-1$ ，可以得到递推方程：
因为使用到了 $dp[0][0]$ ，初始化时需要把 $dp[0][0] = -1$ .因为这样才能让后面直接接上或者直接替换。
其实就是取和不取的问题。
最长上升子序列模型
使用 $dp[i]$ 表示保留 $arr1[i]$ 的最小替换次数，去掉了第二维，因为如果考虑替换的话，需要考虑用哪一个替换了当前的 $arr1[i]$ ，需要增加一维状态。
考虑状态转移， $dp[i]$ 当前不被替换， $dp[i]$ 还可以从 $dp[i-1]$ 转移，如果 $arr1[i] > arr1[i-1]$ ，则可以直接转移。
假设上一个被保留的元素为 $arr1[k]$ ，则此时 $[k + 1, i - 1]$ 全被替换了，则 $dp[i] = dp[k] + i - k - 1$ ，但是也可能全被替换了，可以在数组前面加一个非常小的数，保证这个数一定不会被替换。假设替换的 $j$ 个元素为 $arr2[k], \cdots,arr2[k + j - 1]$ ，则需要满足 $arr1[i - j - 1] \lt arr2[k] $ ， $arr2[k + j - 1] \lt arr1[i]$ .
问题是需要快速找到连续的可以替换的元素，可以使用二分查找找到替换元素的右侧端点，使用 $lower\_bound$ 找到 $arr2$ 中的右侧端点。然后向前枚举替换个数，检查左端点。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| class Solution
{
public:
const static int maxn = 2e3 + 10;
const static int maxm = 1e5 + 10;
const static int INF = 0x3f3f3f3f;
int dp[maxn][maxn];
int makeArrayIncreasing(vector<int> &arr1, vector<int> &arr2)
{
sort(arr2.begin(), arr2.end());
arr2.erase(unique(arr2.begin(), arr2.end()), arr2.end());
int n = arr1.size(), m = arr2.size();
memset(dp, 0x3f, sizeof(dp));
dp[0][0] = -1;
for (int i = 1; i <= n; ++i)
{
for (int j = 0; j <= min(i, m); ++j)
{
if (arr1[i - 1] > dp[i - 1][j])
{
dp[i][j] = min(dp[i][j], arr1[i - 1]);
}
if (j > 0)
{
int tmp = upper_bound(arr2.begin() + j - 1, arr2.end(), dp[i - 1][j - 1]) - arr2.begin();
if (tmp != m)
dp[i][j] = min(dp[i][j], arr2[tmp]);
}
}
}
int ans = -1;
for (int j = 0; j <= min(n, m); ++j)
{
if (dp[n][j] != INF)
{
ans = j;
break;
}
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int maxn = 2e3 + 10;
int INF = 0x3f3f3f3f;
int dp[maxn];
int makeArrayIncreasing(vector<int> &arr1, vector<int> &arr2)
{
sort(arr2.begin(), arr2.end());
arr2.erase(unique(arr2.begin(), arr2.end()), arr2.end());
arr1.insert(arr1.begin(), -1);
arr1.push_back(INF);
int n = arr1.size();
memset(dp, 0x3f, sizeof(dp));
dp[0] = 0;
for (int i = 1; i <= n - 1; ++i)
{
if (arr1[i] > arr1[i - 1])
dp[i] = min(dp[i], dp[i - 1]);
int k = lower_bound(arr2.begin(), arr2.end(), arr1[i]) - arr2.begin();
for (int j = 1; j <= min(k, i - 1); ++j)
{
if (arr2[k - j] > arr1[i - j - 1])
{
dp[i] = min(dp[i], dp[i - j - 1] + j);
}
}
}
return dp[n - 1] == INF ? -1 : dp[n - 1];
}
};
|