题解

全部评论 4

• 

  180****4080

  

  删除

  #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-06-30 来自 浙江

  1
• 

  EORRO 404 不可修复

  删除

  666,没用万能头

  23小时前 来自 江苏

  0
• 

  郑则则

  删除

  #include <iostream>
  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;
  }

  2天前 来自 广东

  0
• 

  175****9056

  

  删除

  #include<bits/stdc++.h>是个好东西

  2025-08-04 来自 山东

  0