比较简单的一道题,但是有一点卡常数。

考虑暴力 DP,定义 $dp(i,j)$ 表示第 $i$ 天到了城市 $j$ 的最高愉悦值。

转移方程即

$$ dp(i,j)=\text{Max}\{dp(i-t,k)+c(j)+extra(i,j)\} $$

其中 $extra(i,j)$ 表示第 $i$ 天 $j$ 城市的额外愉悦值,没有则为 $0$。

考虑到时间范围较大,而且每一次增量较少,考虑用矩乘优化 DP。

我们构造的矩阵为 $5\times n$ 的矩阵,因为 DP 决策的时间增量在 $5$ 以内,而 $\mathcal O((5n)^3)$ 的复杂度还是在允许范围内。

为了方便转移,我们构造的答案矩阵为形如

$$ \left[ \ \begin{matrix} (t,0) & (t,1) & (t,2) & \cdots & (t-1,0) & \cdots & (t-4,n-1) \\ \end{matrix} \ \right] $$

的矩阵,这样答案为一个前缀,而其中的矩阵元素为二元组,我们可以对其标号。

构造转移矩阵的时候需要注意下标的顺序,即 $i$ 与 $j$ 的顺序需要注意,笔者经常犯这样的错误。

对于一条边 $(u,v,w)$ ,我们在矩阵 $(v,(u,w))$ 位置更新为 $c(v)$。具体地可以结合画图来理解。

对于额外的愉悦值,可以参考在今年的国家集训队作业中有一道题的启发,可以把每一个活动,也就是得到愉悦值的时间,从小到大排序,依次加入。通俗地将,就是设置 $k$ 个断点。

在每两个活动之间就是一般化的问题,而对于每一个额外愉悦值,我们都可以在处理完一个前 $i$ 天直接加入答案。

对于卡常,可以参考以下两点:

  • 可以预处理单位矩阵的幂次。
  • 每一次统计答案时,其实答案的矩阵大小为 $1\times 5n$,所以可以减少一重循环。

时间复杂度 $\mathcal O(k\log k+\log T\times (5n)^3+k\times (5n)^2)$

/*
 * Author: chhokmah
 * Date: 2020-08-26 20:12:48
 */
#include <bits/stdc++.h>

using namespace std;

const int N = 50, K = 200;
const int inf = 0x3f3f3f3f;
const long long Inf = 0x3f3f3f3f3f3f3f3f;

int n, m, t, k;
int c[N];

struct Extra {
  int t, x, y;

  bool operator<(const Extra& rhs) const {
    return t < rhs.t;
  }
} ex[K];

int lim;

struct Matrix {
  long long a[250][250];

  long long* operator[](int i) {
    return a[i];
  }

  const long long* operator[](int i) const {
    return a[i];
  }

  Matrix operator*(const Matrix& rhs) const {
    Matrix res;
    for (int i = 0; i < lim; i++)
      for (int j = 0; j < lim; j++) {
        res[i][j] = -Inf;
        for (int k = 0; k < lim; k++)
          res[i][j] = max(res[i][j], a[i][k] + rhs[k][j]);
      }
    return res;
  }
} base[32];

long long ans[1][250], buf[1][250];

void add(Matrix rhs) {
  memset(buf, ~0x3f, sizeof buf);
  for (int i = 0; i < lim; i++)
    for (int j = 0; j < lim; j++)
      buf[0][i] = max(buf[0][i], ans[0][j] + rhs[j][i]);
  memcpy(ans, buf, sizeof ans);
}

int main() {
  freopen("delicacy.in", "r", stdin);
  freopen("delicacy.out", "w", stdout);
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> m >> t >> k;
  lim = 5 * n;
  for (int i = 0; i < n; i++)
    cin >> c[i];
  for (int i = 0; i < lim; i++)
    for (int j = 0; j < lim; j++)
      base[0][i][j] = -Inf;
  for (int i = 0, u, v, w; i < m; i++) {
    cin >> u >> v >> w;
    u--, v--;
    base[0][n * (w - 1) + u][v] = c[v];
  }
  for (int i = n; i < lim; i++)
    base[0][i - n][i] = 0;
  for (int i = 1; i <= 31; i++)
    base[i] = base[i - 1] * base[i - 1];
  for (int i = 0; i < k; i++) {
    cin >> ex[i].t >> ex[i].x >> ex[i].y;
    ex[i].x--;
  }
  memset(ans, ~0x3f, sizeof ans);
  ans[0][0] = c[0];
  sort(ex, ex + k);
  int last = 0;
  for (int i = 0; i < k; i++) {
    int tim = ex[i].t - last;
    for (int j = 0; j <= 31; j++)
      if (tim >> j & 1)
        add(base[j]);
    ans[0][ex[i].x] += ex[i].y;
    last = ex[i].t;
  }
  int tim = t - ex[k - 1].t;
  for (int i = 0; i <= 31; i++)
    if (tim >> i & 1)
      add(base[i]);
  if (ans[0][0] < 0)
    cout << -1 << '\n';
  else
    cout << ans[0][0] << '\n';
  return 0;
}
最后修改:2020 年 08 月 30 日 12 : 30 AM
如果觉得我的文章对你有用,请随意赞赏