「loc - 47725」nomod

18-11-2022
笔记
0 comment

给定一个长度为 $n$ 的序列 $\{a_n\}$ 。要求将这个序列分成互不相交的 $k$ 段，每一段的长度为 $m$ ．记第 $p$ 段的左端点和右端点分别为 $l_p$ ， $r_p$ ．要求最大化 $\displaystyle \sum_{i=1}^k\max_{j=l_i}^{r_i}\{a_j\}$ ．
$n,a_i \leqslant 5 \times 10^5$ ．

这是个 wqs 二分的题，我们先写出没有「 $k$ 段」这个限制的 dp．设 $f_i$ 表示钦定 $i$ 这个位置是某一段的结尾的最大收益．转移即 $\displaystyle f_i = \max_{0 \leqslant j \leqslant i-m} \{dp[j]\}+\max_{i-m+1 \leqslant j \leqslant i} \{a_j\}$ ，后面那个 max 可以单调队列预处理．把 $f_i$ 前缀 max 一下，可以得到 $f_i = \max_{0 \leqslant j \leqslant i-m} \{f_{i-m}+g_i, f_{i-1}\}$ ，其中 $g_i$ 就是第一个方程的第二个 max．

然后就可以直接 wqs 二分了．

#include <iomanip>
#include <iostream>
using std::cin;
using std::cout;
using ll = long long;
#define rep(i,a,b) for (int i(a); i<=(b); ++i)
#define drep(i,b,a) for (int i(b); i>=(a); --i)

int n, m, k, a[500100], que[500100], H, T, idx[500100];
ll dp[500100], mx[500100];

int chk(double e) {
    rep(i,m,n) {
        if (dp[i-m]+mx[i]-e > dp[i-1]) dp[i] = dp[i-m]+mx[i]-e, idx[i] = idx[i-m]+1;
        else dp[i] = dp[i-1], idx[i] = idx[i-1];
    }
    return idx[n];
}

signed main() {
    std::ios::sync_with_stdio(0);
    cin.tie(0);
    cout << std::fixed;
    cout << std::setprecision(0);
    cin >> n >> m >> k;
    rep(i,1,n) cin >> a[i];
    H = 1, T = 0;
    rep(i,1,n) {
        while (H <= T && que[H] <= i-m) H++;
        while (H <= T && a[que[T]] <= a[i]) T--;
        que[++T] = i;
        if (i >= m) mx[i] = a[que[H]];
    }
    double l = -5e5, r = 5e5, mid;
    for (int tc=60; tc--;) {
        if (chk(mid = (l+r)/2) >= k) l = mid;
        else r = mid;
    }
    chk(l);
    cout << dp[n]+l*k << "\n";
}
// mx[i] = max[i-m+1, i]
// dp[i] = max_[0 <= j <= i-m]{dp[j]+max[i-m+1, i]}
// dp[i] = max[0 <= j <= i-m]{dp[j]} + mx[i]
// dp[i] = max{dp[i-1], dp[i-m]+mx[i]}

「apio - 2016」划艇

26-09-2022
笔记
4 comments

link。

Lagrange Interpolation。

朴素的 dp 即设 $f_i(j)$ 表示前 $i$ 个位置，最大值为 $j$ ，位置 $i$ 可选可不选的方案数，转移即 $\displaystyle f_i(j) = f_{i-1}(j)+ [l_i \leqslant j \leqslant r_i]\sum_{k < j} f_{i-1}(k)$ 。把 $j$ 当作自变量，若没有 $l$ ， $r$ 的限制，则可以发现这是个多项式。加上 $l$ ， $r$ ，则是一个分段多项式。比如 $f_1(x) = [l_1 \leqslant x \leqslant r_1]$ ， $\displaystyle \sum_x f_1(x)$ 是分段多项式 $g_1(x)$ ， $f_2(x) = f_1(x) + [l_2 \leqslant x \leqslant r_2] g_1(x-1)$ ，每次前缀和加一次次数。

考虑如何削去 $l$ ， $r$ 的限制，我们可以像 codeforces - 1295f 一样，把区间们化成左闭右开并且把每一个端点当成“标兵”放到数轴上，对相邻标兵构成的区间段（同样是左闭右开）进行考察。容易发现，在同一个段中的多项式并没有分段，我们直接代入 $n+1$ 个点值，就可以确定这个最多 $n$ 次的多项式。

注意，当我们把区间端点离散化后，我们 dp 的状态就变了， $f_i(j)$ 的意义成为了前 $i$ 个位置，前 $j$ 个区间段（注意是值域）拉通了来看的方案数，即多项式在末尾处的取值。

$\texttt{|*****|*****|*****|*****|}\underbrace{{\color{blue}{\texttt {*****}}}}_{\text{cureent }j}{\texttt{|*****|*****|}}$

看到我们研究的这个 $j$ ，段 $j$ 本身就是一个连续的多项式函数，我们需要从段 $j-1$ 的末尾转移过来，这就是为什么我们要求的是段 $j$ 末尾的函数值，即后面的转移需要用。

感觉说得不是很清楚，建议自己再画画图……

const int md = 1e9 + 7;
il int add(int x, int y) {
  if ((x += y) >= md)
    x -= md;
  return x;
}
il int sub(int x, int y) {
  if ((x -= y) < 0)
    x += md;
  return x;
}
il int mul(int x, int y) { return static_cast<long long>(x) * y % md; }
template <class T, class... P> il T mul(T x, T y, P... args) {
  return mul(x, mul(y, args...));
}
il void adds(int &x, int y) {
  if ((x += y) >= md)
    x -= md;
}
il void muls(int &x, int y) { x = static_cast<long long>(x) * y % md; }
int pow(int x, int y) {
  int z(1);
  for (; y; y >>= 1, muls(x, x))
    if (y & 1)
      muls(z, x);
  return z;
}
il int sgn(int n) { return n % 2 ? md - 1 : 1; }
int n, l[1 << 9], r[1 << 9], dat[2 << 9], tot, rec[2 << 9][1 << 9], sum[2 << 9],
    ifct[1 << 9], dp[2 << 9];
int p[1 << 9], q[1 << 9];
int fit(int t, int y[]) {
  int res = 0;
  p[0] = q[n + 2] = 1;
  rep(i, 1, n + 2) p[i] = mul(p[i - 1], sub(t, i));
  drep(i, n + 2, 1) q[i] = mul(q[i + 1], sub(t, i));
  rep(i, 1, n + 2) adds(res, mul(ifct[i - 1], ifct[n + 1 - i], sgn(n - i + 1),
                                 p[i - 1], q[i + 1], y[i]));
  return res;
}
signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n;
  ifct[0] = 1;
  rep(i, 1, n + 2) ifct[i] = mul(ifct[i - 1], i);
  rep(i, 1, n + 2) ifct[i] = pow(ifct[i], md - 2);
  rep(i, 1, n + 1) cin >> l[i] >> r[i];
  rep(i, 1, n + 1) dat[++tot] = l[i], dat[++tot] = ++r[i];
  sort(dat + 1, dat + tot + 1);
  tot = unique(dat + 1, dat + tot + 1) - dat - 1;
  rep(i, 1, n + 1) l[i] = lower_bound(dat + 1, dat + tot + 1, l[i]) - dat;
  rep(i, 1, n + 1) r[i] = lower_bound(dat + 1, dat + tot + 1, r[i]) - dat;
  rep(i, tot + 1) sum[i] = 1;
  rep(i, 1, n + 1) {
    rep(j, l[i], r[i]) {
      rep(k, 1, n + 2) adds(rec[j][k], sum[j - 1]);
      rep(k, 2, n + 2) adds(rec[j][k], rec[j][k - 1]);
      dp[j] = fit(dat[j + 1] - dat[j], rec[j]);
    }
    rep(j, 1, tot + 1) sum[j] = add(sum[j - 1], dp[j]);
  }
  cout << sum[tot] - 1 << "\n";
}

「hdu - 4035」Maze

12-09-2022
笔记
0 comment

设 $dp_x$ 为从 $x$ 走出去的期望步数，可以写出转移 $\displaystyle dp_x = k_x \cdot dp_1 + e_x \cdot 0 + (1 - k_x - e_x) \cdot \sum_{(x, y) \in \mathbb E} \frac{dp_y + 1}{d_x}$ 。这个转移有环，又不能直接高消，于是考虑树的拓扑结构。首先令 $t_x = 1 - k_x - e_x$ ，把转移中那个 $\sum$ 中关于父亲结点的那一项提出来，并且把转移写成 $dp_x = a_x \cdot dp_1 + b_x \cdot dp_{\textit{fa}_x} + c_x$ 的形式，通过叶子结点没有儿子可以解方程，具体过程十分 dirty，参考其他博客。

写一下推导的方向，注意到我们只需要 dp_1 的值，所以我们只需要计算 a_1，c_1 即可。考虑叶子结点没有后继求得叶子结点的 a，b，c 并且经过艰难的推导得到 a_x，b_x，c_x 关于 a_y，b_y，c_y （y 是 x 的后继）的递推式即可。

using db = double;
int n;
bsi<int> adj[1 << 14];
db k[1 << 14], e[1 << 14], t[1 << 14], a[1 << 14], b[1 << 14], c[1 << 14];
void clear() { rep(i, n) bsi<int>().swap(adj[i]); }
bool dfs(int x, int pa) {
  int d = int(adj[x].size());
  a[x] = k[x], b[x] = t[x] / d, c[x] = t[x];
  db sum = 0;
  for (auto y : adj[x])
    if (y != pa) {
      if (!dfs(y, x))
        return 0;
      a[x] += t[x] / d * a[y], c[x] += t[x] / d * c[y], sum += t[x] / d * b[y];
    }
  if (fabs(1 - sum) < 1e-9)
    return 0;
  a[x] /= 1 - sum, b[x] /= 1 - sum, c[x] /= 1 - sum;
  return 1;
}
void run(int runid) {
  int x, y;
  cin >> n;
  rep(n - 1) cin >> x >> y, adj[--x] += --y, adj[y] += x;
  rep(i, n) cin >> k[i] >> e[i], t[i] = 1 - (k[i] /= 100) - (e[i] /= 100);
  cout << "Case " << runid << ": ";
  if (!dfs(0, n) || fabs(1 - a[0]) < 1e-9)
    cout << "impossible\n";
  else
    cout << c[0] / (1 - a[0]) << "\n";
}
signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout << fixed << setprecision(6);
  int tt, kase = 0;
  for (cin >> tt; tt--; clear())
    run(++kase);
}

「codeforces - 1720」

19-08-2022
笔记
0 comment

壹

最近 cq 情况很急急，昨天出去排核酸整了两个半小时，十分无语。提前放假自然是一大好事，但是一个人在家也蛮无聊。不要再涨体重了为好，这一年间他妈 delta 了 10 kilos，算了下 BMI 刚好在「正常」的上界。

贰

前几天在学校训练的时候吃了天天痛肚子的食堂倒闭了，于是和同学一起到校外吃饭。在沙坪坝附近晃悠两圈无意瞥见了一家ガキの頃に我妈经常带我去吃的店（名字叫台湾小竹啥的），进去看到老板（一个长得很抽象的湾湾人）坐在一旁的桌子上。至于我怎么知道那是老板的，只能说メヌー上的抽象画很传神。

叁

教练们在 124 安排了体育活动，生竞去外培自然就只能踢足球。高中的大哥哥们那踢球的风格阿属实汉猛，后场长传直接屮穿底线，总之就是各种生猛。

肆

最重要的放到后面说。

accoders nmsl

link。

A：发现答案上界是 $2$ ，然后捡到三个分讨。
B：发现答案上界总是取得到，然后捡到 pp。
C：发现答案上界是 $\# 1$ ，用最少的步数调整。
D：朴素 dp 用 01-trie 优化。
E：不会。

「joisc 2019 - d2t2」ふたつの料理 Two Dishes

15-08-2022
笔记
0 comment

link。

我要放假

神仙题。

首先可以把两根轴拉成平面（which is a common trick），把决策的过程看作从 $(0, 0)$ 走到 $(n, m)$ ，每次可以往上走或往右走（左下为 (0, 0)，右上是 (n, m)）。考虑相对于我们走出的决策路线表现出了怎样特征的点会对答案造成贡献。对于 A 套餐的操作 $i$ 处理出 $x_i$ ，表示做完了 A 套餐的前 i 个操作，最多还能做到 B 套餐的 x_i 操作，同理处理出 $y_j$ 。

把 $(i, x_i)$ ， $(y_j, j)$ 看作点放到平面上，当 $(i, x_i)$ 在路径上方是获得 $p_i$ 的贡献，当 $(y_j, j)$ 在路径当中或下方时获得 $q_j$ 的贡献。可以先把 p_i 全部加上然后取反转化调整到和 q_j 同样的贡献条件。

那么现在问题是：给出平面，找出一条从 (0, 0) 到 (n, m) 的路径，使得路径当中以及以下的点权和最大。

考虑 dp，设 $f[i][j]$ 为走到 (i, j) 的最优答案。令 $s[i][j]$ 为点 $(i, j)$ 正下方以及自己的点权和，然后我们发现无论从上一行还是上一列转移写出来都不对劲（ $dp[i][j] = dp[i-1][j]+f_1(i, j)+dp[i][j-1]+f_2(i, j)$ 的形式，不好优化），我们考虑从拐点转移（这一步很神奇，同时这一步也是我觉得整道题最 tricky 的地方，但是网上的题解都太草率了，给的转移也不能让我信服），写出的 transitions 是 $\displaystyle dp[i][j] = \max_{k \leqslant j}\{dp[i-1][k]\}+s[i][j]$ ，自己画一个先右再上的折箭头就理解了。

考察转移发现我们有太多的无用转移，注意到平面中权重非 0 的点只有 $O(n+m)$ 个，于是我们考虑非 0 点。首先把 si 拆成 $w_{0, j}+w_{1, j}+\dots +w_{i, j}$ ，这样我们的区间修改就是区间加定值而不是加一个毫无特征的序列了。再考虑前缀 max，因为我们是差分数组，我们只需要将 diff array 中的负项删除，并删除其影响，最后一位即是最大值。

/*
lyddnb
dp[i][j] = max[k <= j]{dp[i-1][k]}+s[i][j]
dp[i]: foreach j, j = premax, j += s[i][j]
*/
int n, m, p[1000100], q[1000100];
ll a[1000100], b[1000100], s[1000100], t[1000100], ans, dif[1000100];
vi<pil> g[1000100];  // g[i](x, y) point (i, x) with weight y
signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> m;
  for (int i = 1; i <= n; ++i) cin >> a[i] >> s[i] >> p[i], a[i] += a[i - 1];
  for (int i = 1; i <= m; ++i) cin >> b[i] >> t[i] >> q[i], b[i] += b[i - 1];
  for (int i = 1; i <= n; ++i) {
    if (a[i] > s[i]) continue;
    int j = upper_bound(b + 1, b + m + 1, s[i] - a[i]) - b;
    ans += p[i], g[i].eb(j, -p[i]);
  }
  for (int i = 1; i <= m; ++i) {
    if (b[i] > t[i]) continue;
    if (b[i] + a[n] <= t[i])
      ans += q[i];
    else {
      int j = upper_bound(a + 1, a + n + 1, t[i] - b[i]) - a;
      g[j].eb(i, q[i]);
    }
  }
  set<int> st;
  for (int i = 0; i <= n; ++i) {
    sort(g[i].begin(), g[i].end());
    for (auto const& [x, y] : g[i]) {
      if (x <= m) {
        if (!st.count(x)) st.insert(x), dif[x] = 0;
        dif[x] += y;
      }
    }
    for (auto const& [x, ignore] : g[i]) {
      if (x > m) continue;
      auto it = st.find(x);
      while (it != st.end() && dif[*it] < 0) {
        ll tmp = dif[*it];
        it = st.erase(it);
        if (it != st.end()) dif[*it] += tmp;
      }
    }
  }
  for (auto x : st) ans += dif[x];
  cout << ans << "\n";
}

标签 dp 下的文章

「loc - 47725」nomod

「apio - 2016」划艇

「hdu - 4035」Maze

「codeforces - 1720」

壹

贰

叁

肆

accoders nmsl

「joisc 2019 - d2t2」ふたつの料理 Two Dishes