A/B's Blog

P2285 [HNOI2004]打鼹鼠

代码 b-a - 1

[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)

代码:
[code lang=”cpp”]
#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);
}
[/code]

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

版权所有 © 呆毛 2018 ⁄ 主题 INN AO