解题思路
第一眼看上去觉得要设计一个三维的 DP,$dp[i][j][k]$ 表示在 $(i,j)$ 这个位置上 $k$ 时刻能够打死的最多的鼹鼠.
但是被数据范围卡死. 完全开不开数组啊.
然后注意到题目中有句话说保证是按照时间递增序输入的.
想一下, 某个鼹鼠能够被打死, 是因为他之前被打死的鼹鼠走过来的.
所以只需要考虑每个鼹鼠之前的若干鼹鼠就可. 只要两个鼹鼠的距离小于它们出现的时刻只差, 那就可以扩展的到.
附上代码
- #include
- #include
- #include
- using namespace std;
- const int maxn = 10003;
- int n, m, x[maxn], y[maxn], t[maxn], Ans = 1, dp[maxn];
- inline int ABS(int x) {
- return x>0 ? x : -x;
- }
- int main() {
- cin>>n>>m;
- for(int i=1; i<=m; i++) {
- cin>>t[i]>>x[i]>>y[i];
- dp[i] = 1;
- for(int j=i-1; j>=1; j--)
- if(ABS(x[j]-x[i])+ABS(y[j]-y[i]) <= t[i]-t[j])
- dp[i] = max(dp[j]+1, dp[i]), Ans = max(Ans, dp[i]);
- }
- printf("%d", Ans);
- }
来源: http://www.bubuko.com/infodetail-2753952.html