CF1144G Two Merged Sequences 题解

· · 题解

Two Merged Sequences

推销我的博客园。

题意

有一个长度为 n 的序列 a，问能否将其拆成一个严格递增子序列和一个严格递减子序列。

若能，输出 YES 并在下一行给出方案，若不能，输出 NO。

输出方案的方法是对于每一位都输出 0 或者 1，若输出 0 表示其在递增序列中，否则在递减序列中。

数据范围

思路

与 xhr 和 cn 巨佬一起完善出来了思路。

考虑使用动态规划。

那么最优化属性呢？很显然，当你把当前位作为当前递增序列的最后一个时，递减序列的最后一个数越大越好，反之，若你把当前位作为当前递减序列的最后一个时，递增序列的最后一个数越小越好。

那么 dp_{i,0} 就表示序列第 i 位作为递增序列时的最大递减序列末项的值，dp_{i,1} 就表示序列第 i 位作为递减序列时的最小递增序列末项的值。

那么转移就很显然了，这里拿 dp_{i,0} 举例，dp_{i,1} 也差不多。

当上一个数小于当前数时，上一个数作为递增序列的最后一个的状态便可以转移至当前数作为递增序列的最后一个的状态。而如果上一个数作为递减序列时的最小递增序列末项的值小于当前数，便可以让当前数接到上一个数作为递减序列时的递增序列之后，那么此时的递减序列末项值为 a_{i-1}。

总结如下：

其中 10^9 和 -10^9 均为极值，可以自行调整，需保证极大值大于 \max\limits _{1\leqslant i \leqslant n} \{a_i\} \leqslant 2 \times 10^5，极小值小于 \min\limits _{1\leqslant i \leqslant n} \{a_i\} \geqslant 0​。

那么怎么求出方案呢？很简单，用个数组记录当前状态是如何转移来的，最后逆推即可。

详细见代码。

复杂度

Code

#include <iostream>

using namespace std;

const int N = 2e5 + 10;

int n, a[N], dp[N][2], lst[N][2]; // lst 用于记录当前状态是如何转移来的，为 0 表示是由 dp[i - 1][0] 转移而来，否则由 dp[i - 1][1] 转移而来

void Output (int x, int y) { // 逆推求方案
  if (!x) {
    return ;
  }
  Output(x - 1, lst[x][y]);
  cout << y << ' ';
}

int main () {
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n, dp[0][0] = 1e9, dp[0][1] = -1e9; // 初始状态
  for (int i = 1; i <= n; i++) {
    cin >> a[i], dp[i][0] = -1e9, dp[i][1] = 1e9;
    // 下面是四种转移方式
    if (a[i - 1] < a[i] || i == 1) {
      dp[i][0] = dp[i - 1][0], lst[i][0] = 0;
    }
    if (dp[i - 1][1] < a[i] && a[i - 1] > dp[i][0]) {
      dp[i][0] = a[i - 1], lst[i][0] = 1;
    }
    if (a[i - 1] > a[i] || i == 1) {
      dp[i][1] = dp[i - 1][1], lst[i][1] = 1;
    }
    if (dp[i - 1][0] > a[i] && a[i - 1] < dp[i][1]) {
      dp[i][1] = a[i - 1], lst[i][1] = 0;
    }
    // cout << dp[i][0] << ' ' << dp[i][1] << '\n'; // Debug
  }
  // 判断目标状态是否合法
  if (dp[n][0] != -1e9) {
    cout << "YES\n";
    Output(n, 0);
  } else if (dp[n][1] != 1e9) {
    cout << "YES\n";
    Output(n, 1);
  } else {
    cout << "NO";
  }
  return 0;
}