NOIP 前 dp 做题小记

1. [BJOI2019] 排兵布阵

   设 \(f(i, j)\) 表示在前 \(i\) 个城堡中总共派遣 \(j\) 个士兵时，可以获得的最大分数。

   初始化：\(\forall 0 \le j \le m\)，\(f(0, j) = 0\)

   答案统计：\(ans = f(n, m)\)

   转移：\(f(i, j) = \max_{0 \le k \le j} f(i - 1, j - k) + g(i, k)\)。其中 \(g(i, k)\) 表示向第 \(i\) 个城堡派遣 \(k\) 个士兵能获得的分数。这里就是在枚举在第 \(i\) 个城堡中投入的兵力 \(k\) 来转移。

   \(g(x, y)\)（\(0 \le x \le n\)，\(0 \le y \le m\)）可以在 \(O(n(s \log s + m))\) 的时间内预处理：

   for(int i = 1; i <= n; i++)
   {
       deque<int> tmp;
       for(int j = 1; j <= s; j++)
           tmp.push_back(a[j][i]);
       sort(tmp.begin(), tmp.end());
       int cnt = 0;
       for(int j = 0; j <= m; j++)
       {
           while(!tmp.empty() && j > tmp.front() * 2)
           {
               cnt++;
               tmp.pop_front();
           }
           g[i][j] = cnt * i;
       }
   }
   

   时间复杂度分析：预处理 \(g\) 花费 \(O(n(s \log s + m))\)，dp 状态数 \(O(nm)\)，单次转移的时间复杂度为 \(O(m)\)，总时间复杂度为 \(O(nm^2)\)（忽略了预处理的时间复杂度，因为不是瓶颈）。可以获得 40 分。

   ---

   优化：

   从决策的角度来考虑。向第 \(i\) 个城堡投入兵力时，并不是每多派遣一个士兵，在此城堡中获得的分数都会增加。设 \(g(i, j)\) 表示向第 \(i\) 投入兵力第 \(j\) 多的人派遣的士兵的数量（与上文的 \(g\) 的含义不同），则我方投入的兵力只有在恰好达到某个 \(2g(i, j) + 1\) 时，在此城堡上得到的分数才会增加。这启发我们转移时不是枚举向城堡中投入的人数，而是枚举要超过多少人的兵力的两倍。这样转移的时间复杂度就从 \(O(m)\) 降到了 \(O(s)\)，总时间复杂度降到 \(O(nms)\)，可以通过。

   另一种思考方法是把问题转化为分组背包问题。按城堡来分组，每个组有 \((s + 1)\) 个物品，第 \(i\) 组第 \(j\) 个物品代表我方在第 \(i\) 个城堡中打败了 \(j\) 个人，据此可以得出其花费为 \(2g(i, j) + 1\)，价值为 \(ij\)。

2. P4310 绝世好题

   注意“子序列”不一定是连续的。

   • \(O(n^2)\) 做法

     设 \(f(i)\) 表示以第 \(i\) 个元素结尾的最长合法子序列的长度，显然 \(f(i) = \max_{1 \le j < i \and a_i \operatorname{and} a_j \neq 0} \{f(j) + 1\}\)

   • \(O(n)\) 做法

     从位运算的角度出发。

     设 \(f(i)\) 表示结尾元素的第 \(i\) 个二进制位为 \(1\) 时，最长的合法子序列的长度。

     计算 \(f(i)\) 时，枚举 \(a_i\) 的第 \(j\) 位二进制位为 \(1\) 的 \(j\)，用 \(f(j) + 1\) 来更新 \(tmp\)，然后再反过来用 \(tmp\) 来更新 \(f(j)\)。

     for(int i = 0; i < n; i++)
     {
         int tmp = 0;
         for(int j = 0; (1 << j) <= a[i]; j++)
             if(a[i] & (1 << j)) tmp = max(tmp, f[j] + 1);
         for(int j = 0; (1 << j) <= a[i]; j++)
             if(a[i] & (1 << j)) f[j] = tmp;
         ans = max(ans, tmp);
     }
     

3. [JSOI2016] 最佳团体

   题意：给定一棵树，每个节点 \(i\) 有费用和权值。选择一个包含根节点且有 \((K + 1)\) 个点的连通块，使得节点总权值与总费用的比最大。

   分数规划

4. P1453 城市环路

   题意：求基环树的最大带权独立集。

   树上最大带权独立集是树形 dp 经典题目：没有上司的舞会。回忆一下做法：设 \(f(u, 1/0)\) 分别表示选/不选 \(u\) 时，在 \(T(u)\) 中能获得的最大权值。转移方程如下：

   \[f(u, 1) = \sum_{v \in son(u)} f(v, 0) \\ f(u, 0) = \sum_{v \in son(u)} \max(f(v, 1), f(v, 0)) \]

   而在这道题中，图多了一条边，形成了一棵基环树。如何转化到树上问题呢？

   由于基环树有且只有一个环，因此删去环上的任意一条边后，基环树就变成了真正的树。不妨假设删去的边是 \((x, y)\)，我们在删完边后的图上做树形 dp 求树上最大带权独立集。但考虑到删去的边的限制，\(x\) 和 \(y\) 这两个节点不能同时选择，这需要在 dp 中有所体现。

   修改是不难的：只需分别以 \(x\) 和 \(y\) 为根各做一次树形 dp，则答案为 \(\max(f(x, 0), f(y, 0))\)。这相当于分别钦定了不选择 \(x\) 或不选择 \(y\)，这样得到的答案一定合法，并且是考虑周全的。

   提交记录