[dp 记录] CF1342F

trick：dp 数组定义域与值域的互换。

基本复读魏老师题解。

题意：

将 \(n\) 数合并为 \(m\) 集合，每个集合取出一个代表元，使得（代表元下标，集合和）构成偏序关系。最大化 \(m\) 并输出方案。

\(O(n^2 3^n)\)。那个数据范围很鬼畜。

朴素的 dp 需要记录已选元素、上一个集合的代表元、上个集合和。然后会发现和一维太大了。但是整个 dp 的值域仅有 \(n\) 大小。

注意到若 \(dp_{i,j,k} = dp_{i,j,k'}\) 且 \(k < k'\)，则 \(k'\) 无用。因此只用对每个 \(t\) 记录使 \(dp_{i,j,k}=t\) 的最小 \(k\)。然后值域就忽然小到能做了。

这样子本质是贪心排除了一些不可能成为答案的集合。

转移时也可以贪心一些：枚举补集用当前状态更新下一个状态，则只用贡献给 最小大于上代表元的新集合内数字 处。仍是贪心显然。

代码有点长但思路很清晰。这题不错，但感觉知道 trick 后还是平常了。

#include <cstdio>
#include <tuple>
#include <vector>
using namespace std;
const int M = 16, inf = 1e9 + 7;
int f[1 << M][M][M]; // f[i][j][k] := 已选数集 i，最后一个集合代表元为 j，已有 k 集合，时的最小最后集合和
tuple<int, int, int> p[1 << M][M][M];
int a[M], s[1 << M];
vector<pair<int, int> > ans;
void solve() {
  int n; scanf("%d", &n);
  for(int i = 0; i < n; i++) scanf("%d", &a[i]);
  int all = (1 << n) - 1;
  for(int i = 0; i < 1 << n; i++)
    for(int j = 0; j <= n; j++)
      for(int k = 0; k <= n; k++)
        f[i][j][k] = inf;
  f[0][0][0] = 0;
  for(int i = 0; i < 1 << n; i++) s[i] = 0;
  for(int i = 0; i < n; i++) s[1 << i] = a[i];
  for(int i = 0; i < n; i++)
    for(int j = 0; j < 1 << n; j++)
      if((j >> i) & 1) s[j] += s[j ^ (1 << i)];
  for(int i = 0; i < 1 << n; i++) 
    for(int j = 0; j < n; j++)
      for(int k = 0; k < n; k++) {
        if(f[i][j][k] == inf) continue;
        int U = all ^ i;
        for(int T = U; T; T = (T-1) & U) {
          if(s[T] > f[i][j][k] && (T >> j)) {
            int t = __builtin_ctz(T >> j << j) + 1; // 此处 +1 平移
            if(f[i+T][t][k+1] > s[T]) {
              f[i+T][t][k+1] = s[T];
              p[i+T][t][k+1] = make_tuple(i, j, k);
            }
          }
        }
      }
  for(int t = n; t >= 1; t--) {
    for(int i = 1; i <= n; i++)
      if(f[all][i][t] != inf) {
        ans.clear();
        auto dfs = [&](auto self, tuple<int, int, int> t) -> void {
          int msk = get<0>(t), pl = get<1>(t), num = get<2>(t);
          if(!msk) return;
          self(self, p[msk][pl][num]);
          int x = msk - get<0>(p[msk][pl][num]);
          for(int i = 0; i < n; i++) {
            if(x & (1 << i) && i+1 != pl) ans.push_back(make_pair(i+1, pl));
          }
        } ;
        dfs(dfs, make_tuple(all, i, t));
        printf("%d\n", ans.size());
        vector<bool> del(n+1);
        auto find = [&](int x) -> int {
          int ans = 1;
          for(int i = 1; i < x; i++) ans += del[i] == 0;
          return ans;
        } ;
        for(int i = 0; i < ans.size(); i++)
          printf("%d %d\n", find(ans[i].first), find(ans[i].second)),
          del[ans[i].first] = 1;
        return;
      }
  }
}
int main() {
  int T; scanf("%d", &T);
  while(T--) {
    solve();
  }
}