题目链接

BZOJ2794

思路要点

考虑将所有的询问离线后进行统一处理。

首先不考虑 $b$ 的限制,那么只需要考虑 $a\leq m$ 这个偏序关系。

为了减少重复的计算,考虑将物品和询问分别按照 $a$ 和 $m$ 排序,然后从小到大依次更新背包即可。

那么显然只需要存在一组 $b$ 满足即可,也就是只需要满足所有的合法方案中每个方案的最小的 $b$ 的最大值 $>m+s$ 即可。

所以我们考虑更换 $DP$ 的状态为 $f[i]$表示之前所有的物品,和为 $i$ 的合法方案中 $b$ 最小值的最大值。

这样只需要在处理完所有物品后查看当前的$f[c]$是否$<m+s$即可,正确性显然。

时间复杂度 $O(nq)$

代码

#include <bits/stdc++.h>
#define For(i, s, t) for (int i = s; i <= t; i++)
#define inf 0x3f3f3f3f

using namespace std;

const int N = 1005;
const int M = 1e6 + 5;
const int S = 1e5;

struct Query {
  int m, k, s, id;
} query[M];

struct Project {
  int a, b, c;
} p[N];

int n, q, mxz;
int f[S + 5];
int ans[M];

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  memset(f, ~0x3f, sizeof f);
  f[0] = inf;
  mxz = 0;
  cin >> n;
  For (i, 1, n) {
    cin >> p[i].c >> p[i].a >> p[i].b; 
    mxz += p[i].c;
  }
  cin >> q;
  For (i, 1, q) {
    cin >> query[i].m >> query[i].k >> query[i].s;
    query[i].id = i;
  }
  sort(p + 1, p + 1 + n, [](Project lhs, Project rhs) {
    return lhs.a < rhs.a;
  });
  sort(query + 1, query + 1 + q, [](Query lhs, Query rhs) {
    return lhs.m < rhs.m;
  });
  int lfp = 1;
  For (i, 1, q) {
    while (lfp <= n && p[lfp].a <= query[i].m) {
      for (int j = min(mxz, S); j >= p[lfp].c; j--) {
        f[j] = max(f[j], min(f[j - p[lfp].c], p[lfp].b));
      }
      lfp++;
    }
    if (f[query[i].k] > query[i].m + query[i].s) {
      ans[query[i].id] = 1;
    }
  }
  For (i, 1, q) {
    cout << (ans[i] ? "TAK" : "NIE") << '\n';
  }
  return 0; 
}

后言

  • 所有的有关和为k的问题都大概率可以转化为背包。
  • 如果有多个限制条件,且这些限制条件都满足某种偏序,那么可以考虑先排序其中一维,在考虑第二维。
  • 问题复杂时,且所有的限制条件相对独立,可以先分开考虑,在合在一起考虑。
最后修改:2020 年 03 月 21 日 10 : 42 PM
如果觉得我的文章对你有用,请随意赞赏