| 题目名称 | 30. [FZYZOJ 1273] 坦克游戏 |
|---|---|
| 输入输出 | gametk.in/out |
| 难度等级 | ★★☆ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 10 |
| 题目来源 |
 cqw
于2008-04-23加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：8， 提交：32， 通过率：25% | ||||
 YGOI_真神名曰驴蛋蛋 |
100 | 0.021 s | 0.28 MiB | C++ |
 烈火青龙 |
100 | 0.087 s | 0.28 MiB | C++ |
 ytrytr |
100 | 0.098 s | 2.77 MiB | Pascal |
 天一阁 |
100 | 0.117 s | 2.77 MiB | Pascal |
 龙行天下 |
100 | 0.120 s | 2.50 MiB | Pascal |
 FoolMike |
100 | 0.220 s | 40.40 MiB | C++ |
 根管理员 |
100 | 0.482 s | 29.46 MiB | C++ |
|
神威难藏于泪 |
100 | 0.777 s | 25.52 MiB | C++ |
 ....0.. |
10 | 0.010 s | 0.29 MiB | C |
|
....0.. |
10 | 0.012 s | 0.29 MiB | C |
| 本题关联比赛 | |||
| 2008haoi模拟训练2 | |||
| 关于 坦克游戏 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
给一份题解：
首先我们规定，攻击某个目标第一次进入视野时才攻击他。 设dp[i][j][k]表示坦克在(i,j)，用时k秒的最大得分，每次移动，视野只扩大一个线状区域，枚举攻击几个目标，贪心选择即可。 注意，从(i,j)移动到(i+1,j)或(i,j+1)的转移要一起处理。 总体复杂度粗略估算是$O(n^{2}tr)$，约为$O(n^{5})$ | ||||
|
| ||||
|
终于过了_(:з」∠)_合影留念
YGOI_真神名曰驴蛋蛋
2016-06-14 16:15
6楼
| ||||
|
数据范围实际上是N,M<=50。。。
 thomount
2015-09-18 22:35
5楼
| ||||
|
| ||||
|
回复 @天一阁 :
Orzzzzzzzzzzzzzzzzzzzzzzzz给六年来第一个A掉这题的跪……  cstdio
2014-08-14 10:32
3楼
| ||||
|
动态规划，好题！
天一阁
2014-08-13 19:33
2楼
| ||||
|
哪位神犇把这题秒了啊，或给份题解。。
 GDFRWMY
2014-03-24 21:04
1楼
| ||||
AntiLeaf【问题描述 】
NOI2008公司最近推出了一款新的坦克游戏。在游戏中，你将操纵一辆坦克，在一个 N × M 的区域中完成一项任务。在此的区域中，将会有许多可攻击的目标，而你每摧毁这样的一个目标，就将获得与目标价值相等的分数。只有获得了最高的分数，任务才算完成。同时，为了增加游戏的真实性和难度，该游戏还做了以下的限制：
• 坦克有射程 r 的限制。为方便计算，射程 r 规定为：若坦克位于 (x,y) 格，则它可攻击的目标 (x1,y1) 必须满足 |x-x1|,|y-y1| ∈ [0,r] 。
• 对坦克完成任务的时间有严格限制，规定为 t 秒。其中，坦克每进行一次移动都需 1 秒的时间，每攻击一个目标也需 1 秒的时间。时间一到 t 秒，便对此次任务进行记分。
• 坦克最初位于左上角，且移动方向只准是向右或向下，每次只允许移动一格。
在以上的限制条件下，要完成该任务便成为了一件很难事情。因此，你必须为此编写一个程序，让它助你完成这个艰巨的任务。
【输入格式】
输入文件： gametk.in
第一行右四格整数 N 、 M 、 r 、 t ，分别表示区域的长、宽，以及射程和完成任务时间。
接下来 N 行是一格 N×M 的矩阵，对应每个位置上目标的价值。 1 ≤ N 、 M ≤ 50 ， 1 ≤ r ≤ 100 ， 1 ≤ t ≤ 2500 。
【输出格式】
输出文件： gametk.out
输出文件仅一个数 max ，即该任务中可得到的最高分数。
【输入样例】
5 5 2 7
0 5 0 0 4
0 0 0 0 2
0 0 0 0 0
0 0 0 0 0
5 0 3 0 11
【输出样例】
21
UPD:数据中$n,m \leq 50$，2017.10.6 Mike修正题目描述