Gravatar
FoolMike
积分:5200
提交:1165 / 2240
给一份题解:
首先我们规定,攻击某个目标第一次进入视野时才攻击他。
设dp[i][j][k]表示坦克在(i,j),用时k秒的最大得分,每次移动,视野只扩大一个线状区域,枚举攻击几个目标,贪心选择即可。
注意,从(i,j)移动到(i+1,j)或(i,j+1)的转移要一起处理。
总体复杂度粗略估算是$O(n^{2}tr)$,约为$O(n^{5})$

Gravatar
AntiLeaf
积分:3393
提交:1527 / 4369

Gravatar
YGOI_真神名曰驴蛋蛋
积分:1978
提交:671 / 1901
终于过了_(:з」∠)_合影留念

Gravatar
thomount
积分:1493
提交:304 / 820
数据范围实际上是N,M<=50。。。

Gravatar
天一阁
积分:1739
提交:544 / 1314

Gravatar
cstdio
积分:4755
提交:1198 / 2108
回复 @天一阁 :
Orzzzzzzzzzzzzzzzzzzzzzzzz给六年来第一个A掉这题的跪……

Gravatar
天一阁
积分:1739
提交:544 / 1314
动态规划,好题!

Gravatar
GDFRWMY
积分:318
提交:81 / 216
哪位神犇把这题秒了啊,或给份题解。。