I've been working on this problem from JOISC 2020:
Problem summary
You're given two arrays $$$a$$$ and $$$b$$$ of length $$$2n$$$. You have to pick exactly $$$n$$$ elements from each array to form a sequence of $$$2n$$$ total elements (alternating picks between the two arrays), such that the resulting sequence is non-decreasing. If possible, also print such a sequence using 'A' and 'B' to indicate from which array each element was chosen.
Dynamic programming
The following dynamic programming solution is fairly obvious:
$$$\text{dp}[i][j][k]$$$ denotes whether it's possible to get an increasing subsequence from the first $$$i$$$ elements picking exactly $$$j$$$ elements from $$$a$$$, with $$$k$$$ being $$$1$$$ meaning you're forced to pick $$$a[i]$$$ and $$$k$$$ being $$$0$$$ meaning you're forced to pick $$$b[i]$$$.
These 'forcing' condition allow us to check monotonicity easily, because now looking at a previous dynamic programming state to check whether we're $$$\ge$$$ than it will be easy. Transitions are:
$$$\text{dp}[i][j][k]={\text{dp}[i-1][j-k][1]\,\text{and}\, a[i-1]\le \text{arr}[k][i]} \,\text{or}\,{\text{dp}[i-1][j-k][0]\,\text{and}\, b[i-1]\le \text{arr}[k][i]}$$$
where $$$\text{arr}[0] = b$$$ and $$$\text{arr}[1] = a$$$.
dp[0][0][0] = dp[0][0][1] = true;
int *arr[] = {b, a};
for (int i = 1; i <= n << 1; ++i) {
for (int j = 0; j <= n; ++j) {
for (int k = 0; k < 2; ++k) {
if (j - k >= 0) {
dp[i][j][k] = (dp[i - 1][j - k][1] && a[i - 1] <= arr[k][i]) || (dp[i - 1][j - k][0] && b[i - 1] <= arr[k][i]);
}
}
}
}
Full solution
Okay, so this is where the editorial mentions something
