题解

全部评论 1

• 

  魔丸哪吒（突击手）

  

  删除

  #include <stdio.h>
  #include <string.h>
  #include <iostream>
  #include <algorithm>
  #include <queue>
  using namespace std;
  const int N = 1010;
  int n, m, p;
  int s[N][N], cost[N];
  int f[N], g[N][N];
  struct Node
  {
  int v, i, j;
  bool operator < (const Node & W) const
  {
  return v < W.v;
  }
  };
  priority_queue<Node> heap[N];
  int get(int x)
  {
  x %= n;
  if (x <= 0)
  {
  x += n;
  }
  return x;
  }
  int main(void)
  {
  scanf("%d%d%d", &n, &m, &p);
  for (int i = 1; i <= n; i++)
  {
  for (int j = 1; j <= m; j++)
  {
  scanf("%d", &s[i][j]);
  }
  }
  for (int i = 1; i <= m; i++)
  {
  for (int j = 1; j <= n; j++)
  {
  if (j == 1)
  {
  s[j][i] += s[n][i - 1];
  }
  else
  {
  s[j][i] += s[j - 1][i - 1];
  }
  }
  }
  memset(f, -0x3f, sizeof f);
  memset(g, -0x3f, sizeof g);
  f[0] = 0;
  for (int i = 1; i <= n; i++)
  {
  scanf("%d", &cost[i]);
  }
  for (int i = 1; i <= n; i++)
  {
  g[0][i] = -cost[get(i + 1)];
  heap[get(0 - i)].push({ g[0][i], 0, i });
  }
  for (int i = 1; i <= m; i++)
  {
  for (int j = 1; j <= n; j++)
  {
  auto& h = heap[get(i - j)];
  while (h.size())
  {
  auto t = h.top();
  if (i - p > t.i)
  {
  h.pop();
  }
  else
  {
  f[i] = max(f[i], s[j][i] + t.v);
  break;
  }
  }
  }
  for (int j = 1; j <= n; j++)
  {
  g[i][j] = f[i] - s[j][i] - cost[get(j + 1)];
  heap[get(i - j)].push({ g[i][j], i, j });
  }
  }
  int res = 0;
  for (int i = 0; i <= m; i++)
  {
  res = max(res, f[i]);
  }
  cout << res << endl;
  return 0;
  }

  2025-03-02 来自 浙江

  0
  • 

    老登转世

    回复魔丸哪吒（突击手）

    删除

    ????

    2025-04-12 来自 四川

    0