bzoj1207: [HNOI2004]打鼹鼠(DP)

1207: [HNOI2004]打鼹鼠

题解：

　　这是一道简单的DP

　　设立f[i]表示处理到第i只鼹鼠时被打死鼹鼠的最大数目：

　　　　　f[i]=max(f[i],f[j]+1);

　　注意一下：题目说明一开始可以选任意一个位置作为起点，那么肯定选择一个一开始就会出现鼹鼠的地方，所以最后ans++

水代码：

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cstdlib>
 4 #include<cmath>
 5 #include<algorithm>
 6 using namespace std;
 7 int t[11000],x[11000],y[11000];
 8 int f[11000];//处理d到第i只鼹鼠时被打死鼹鼠的最大数目 
 9 int n,m;
10 int main()
11 {
12     memset(f,0,sizeof(f));
13     scanf("%d%d",&n,&m);
14     for(int i=1;i<=m;i++)scanf("%d%d%d",&t[i],&x[i],&y[i]);
15     for(int i=1;i<=m;i++)
16         for(int j=i-1;j>=1;j--)
17             if((abs(x[i]-x[j])+abs(y[i]-y[j]))<=(t[i]-t[j]))
18                 f[i]=max(f[i],f[j]+1);
19     int ans=0;
20     for(int i=1;i<=m;i++)ans=max(ans,f[i]);
21     printf("%d
",ans+1);
22     return 0;
23 }