特殊未来 2021-07-03 19:54 采纳率: 25%
浏览 33

连续好几次TL了,这种题有没有什么简便算法?

题目描述
H国的土地被划分为N行M列的土地块,每个地块都算出了相应的土地价值。首都被认为是H国中的一个由C行C列的土地块构成的正方形区域。请你帮忙寻找一个合适的位置建立首都,使得首都所占领的位置的土地价值和最高。

输入格式
第1行:三个正整数N,M,C,表示H国土地块构成N行M列的区域,首都是C行C列的正方形区域。 第2~N+1行:每一行包含M个整数,表示H国每个地块的价值。价值可能为负数。

输出格式
第1行,两个整数X,Y,表示首都左上角土地块的位置。

数据范围与提示
对于100%的数据N,M<=3000,-1,000,000,000<=价值<=1,000,000,000。
输入样例
3 4 2
1 2 3 1
-1 9 0 2
2 0 1 1
输出样例
1 2

  • 写回答

1条回答 默认 最新

  • e_Gravity 2023-01-10 10:20
    关注

    这是一道二维前缀和的题,通过前缀和预处理,可以在O(1)的时间算出某个正方形的价值。
    只要枚举正方形的右下角或者左上角,时间复杂度总共为O(N^2)

    评论

报告相同问题?

悬赏问题

  • ¥15 微信小程序协议怎么写
  • ¥15 c语言怎么用printf(“\b \b”)与getch()实现黑框里写入与删除?
  • ¥20 怎么用dlib库的算法识别小麦病虫害
  • ¥15 华为ensp模拟器中S5700交换机在配置过程中老是反复重启
  • ¥15 java写代码遇到问题,求帮助
  • ¥15 uniapp uview http 如何实现统一的请求异常信息提示?
  • ¥15 有了解d3和topogram.js库的吗?有偿请教
  • ¥100 任意维数的K均值聚类
  • ¥15 stamps做sbas-insar,时序沉降图怎么画
  • ¥15 买了个传感器,根据商家发的代码和步骤使用但是代码报错了不会改,有没有人可以看看