代码

P2285 [HNOI2004]打鼹鼠

[success]原题 https://www.luogu.org/problem/show?pid=2285[/success]

我的解法:
在学校举办的模拟赛上的题目,最近一直在做DP题...然后结果当时想了没半个小时AC了,
回来想在洛谷再A一次,结果等级居然说是提高+/省选- = =...这个分级有点水啊...

做法也很简单,从时间顺序逆着来DP,看这个点在规定时间能到达哪几个点
dp[i] = max{dp[j]|time(i, j) >= dist(i, j)}
然后还得特判...n==m==0 答案是2????????无语...
O(m^2)

代码:

#include<cstdio>
#include<iostream>
#define MAXN 1050
#define MAXM 10050
using namespace std;
int v[MAXM];
int mo[MAXM][3];
int n, m;

int fabs(int i){
	return (i)<0?-(i):(i);
}

int dist(int i, int j){
	return fabs(mo[i][1] - mo[j][1]) + fabs(mo[i][2] - mo[j][2]);
}

int main(){
	int ans = 1;
	scanf("%d%d", &n, &m);
	if (n == 0 && m == 0){
		printf("2");
		return 0;
	}
	for (int i = 0; i < m; i++) scanf("%d%d%d", &mo[i][0], &mo[i][1], &mo[i][2]);
	v[m - 1] = 1;
	for (int i = m - 1; i >= 0; i--){
		int adds = -1;
		for (int j = i + 1; j < m; j++) if (mo[j][0] - mo[i][0] >= dist(i, j)) adds = max(adds, v[j]);
		v[i] = max(adds + 1, 1);
	}
	for (int i = 0; i < m; i++) ans = max(ans, v[i]);
	printf("%d", ans);
}

是不是除了dp我还得再做做其他类型的题目??

b-a
我还没有学会写个人说明!
查看“b-a”的所有文章 →

1 条评论

  1. 1

    好!!!

Leave a Reply

Your email address will not be published. Required fields are marked *

相关推荐