Similarity of Necklaces 2

题意概述

给定四个数组$M, P, L, R$,要求构造一个数组$T$,使得
$$\sum_{i=1}^N M_iT_i=0 \; (L_i \le T_i \le R_i)$$
求$\sum_{i=1}^N P_iT_i$的最大值。
数据范围:$1 \le N \le 200, \; 1 \le M_i \le 20, \; 0 \le P_i \le 10^5, \; -25 \le L_i \lt R_i \le 25$。

算法分析

令$D_i=T_i-L_i$,那么限制条件变为$\sum_{i=1}^N M_iD_i=-\sum_{i=1}^N M_iL_i \; (0 \le D_i \le R_i-L_i)$,要求的值变为$\sum_{i=1}^N P_iD_i+\sum_{i=1}^N P_iL_i$。这就相当于有$N$种物品,第$i$种物品有$(R_i-L_i)$个,每一个的体积为$M_i$,价值为$P_i$,背包的体积为$-\sum_{i=1}^N M_iL_i$,求物品恰好装满背包时的最大价值。这是分组背包问题,用单调队列优化DP即可。

代码

#include <cstdio>
#include <cstring>

int min(int a, int b) {
  return a < b ? a : b;
}

static const int N = 205;
int p[N], m[N], u[N], l[N];
int f[N << 10], q1[N << 10], q2[N << 10];

int main() {
  int n;
  while (~ scanf("%d", &n)) {
    int v = 0, w = 0;
    for (int i = 0; i < n; ++ i) {
      scanf("%d%d%d%d", &p[i], &m[i], &l[i], &u[i]);
      if (l[i]) u[i] -= l[i], v -= l[i] * m[i], w -= l[i] * p[i];
    }
    memset(f, -0x3f, sizeof f), f[0] = 0;
    for (int i = 0; i < n; ++ i) {
      u[i] = min(u[i], v / m[i]);
      for (int d = 0; d < m[i]; ++ d) {
        int l = 1, r = 0;
        for (int j = 0; j <= (v - d) / m[i]; ++ j) {
          int val = f[j * m[i] + d] - j * p[i];
          while (l <= r && q1[r] < val) -- r;
          q2[++ r] = j, q1[r] = val;
          if (j - q2[l] > u[i]) ++ l;
          f[j * m[i] + d] = q1[l] + j * p[i];
        }
      }
    }
    printf("%d\n", f[v] - w);
  }
  return 0;
}

RegMs If

418 I'm a teapot

Leave a Reply

Your email address will not be published. Required fields are marked *