题解：P7652 [BalticOI 1996] A NICE SEQUENCE (Day 1)

Warren1022 · 2025-11-06 22:19:44 · 题解

P7652 [BalticOI 1996] A NICE SEQUENCE (Day 1)题解

题目传送门

本蒟蒻的第一个灰题题解。

题目简述

本题要求将一个整数序列划分为尽可能少的子序列，每个子序列必须满足：

1. 至少包含 2 个元素。
2. 是非递增或非递减的。
3. 每个元素恰好属于一个子序列。

解题思路

采用深度优先搜索( DFS )配合剪枝策略：

• 逐个尝试将元素分配到现有子序列或创建新子序列。
• 每次分配时检查单调性约束。
• 通过剪枝避免无效搜索路径。
• 记录最优解。

  代码实现

  #include <bits/stdc++.h>
  using namespace std;
  int n;
  vector<int> arr;
  vector<int> ans;
  vector<vector<int>> S;
  int minK = INT_MAX;
  vector<int> bans;
  bool check(const vector<int>& s) {
  if (s.size() < 2) return false;
  bool inc = true, dec = true;
  for (int i = 1; i < s.size(); i++) {
      if (s[i] < s[i-1]) inc = false;
      if (s[i] > s[i-1]) dec = false;
  }
  return inc || dec;
  }
  void dfs(int idx, int k) {
  if (k >= minK) return; 
  if (idx == n) {
      for (const auto& s : S) {
          if (s.size() < 2 || !check(s)) return;
      }
      if (k < minK) {
          minK = k;
          bans = ans;
      }
      return;
  }
  for (int i = 0; i < S.size(); i++) {
      if (!S[i].empty()) {
          S[i].push_back(arr[idx]);
          if (check(S[i])) {
              int old = ans[idx];
              ans[idx] = i + 1;
              dfs(idx + 1, k);
              ans[idx] = old;
          }
          S[i].pop_back();
      }
  }
  if (S.size() < n / 2) {
      S.push_back({arr[idx]});
      ans[idx] = S.size();
      dfs(idx + 1, S.size());
      S.pop_back();
      ans[idx] = 0;
  }
  }
  int main() {
  cin >> n;
  arr.resize(n);
  ans.resize(n, 0);
  for (int i = 0; i < n; i++) {
      cin >> arr[i];
  }
  if (n < 2) {
      cout << 0 << endl;
      return 0;
  } 
  S.clear();
  dfs(0, 0);
  if (minK == INT_MAX) {
      cout << 0 << endl;
  } else {
      cout << minK << endl;
      for (int i = 0; i < n; i++) {
          cout << arr[i] << " " << bans[i] << endl;
      }
  }
  return 0;
  }

经蒟蒻检验，此代码经过剪枝可以通过本题。

祝dalao们生活美满✿✿ヽ(°▽°)ノ✿~~~。