BZOJ 1207 [HNOI2004]打鼹鼠：dp【类似最长上升子序列】

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1207

题意：

　　有一个n*n的网格，接下来一段时间内会有m只鼹鼠出现。

　　第i只鼹鼠会在tim[i]秒出现，位置为(x[i],y[i])。数据保证tim[i]递增给出。

　　你有一个打鼹鼠的机器，初始位置可以自定。机器每秒钟只能原地不动或者走一格。在某一秒机器位置与鼹鼠出现的位置相同时，认为这个鼹鼠被打到。

　　问你最多能打多少鼹鼠。

题解：

　　乍一看和HDU 1176 免费馅饼很像：

　　　　dp[i][x][y] = 第i秒在(x,y)最多打的鼹鼠数

　　但是时间和空间都会爆。。。

　　for循环时间：O(n^4 * m)

　　改为记忆化搜索：O(n^2 * m^2)

　　（时间 = 枚举起始位置 * 求dp）

　　打鼹鼠有一个和最长上升子序列相似的性质：

　　　　打鼹鼠：如果tim[i] < tim[j]，那么鼹鼠j只可能在鼹鼠i出现之后打。

　　　　LIS：如果i < j，那么s[j]只可能在考虑完s[i]之后加入答案。

　　表示状态：

　　　　dp[i] = max hit

　　　　i：打了第i只鼹鼠

　　找出答案：

　　　　max dp[i]

　　如何转移：

　　　　dp[i] = max dp[j] + 1 (j < i, tim[i]-tim[j] >= manhattan(ci,cj))

　　　　（j在i之前，并且可以在限定时间内从j到达i（曼哈顿距离））

　　边界条件：

　　　　set dp = 1

　　　　至少打了自己。

AC Code:

 // state expression:

 // dp[i] = max hit

 // i: ith mole is dead

 //

 // find the answer:

 // max dp[i]

 //

 // transferring:

 // dp[i] = max dp[j] + 1 (tim[i]-tim[j] >= manhattan(ci,cj))

 //

 // boundary:

 // set dp = 1

 #include <iostream>

 #include <stdio.h>

 #include <string.h>

 #include <stdlib.h>

 #define MAX_M 10005

 using namespace std;

 int n,m;

 int ans=;

 int x[MAX_M];

 int y[MAX_M];

 int tim[MAX_M];

 int dp[MAX_M];

 void read()

 {

     cin>>n>>m;

     for(int i=;i<m;i++)

     {

         cin>>tim[i]>>x[i]>>y[i];

     }

 }

 void solve()

 {

     for(int i=;i<m;i++)

     {

         dp[i]=;

         for(int j=;j<i;j++)

         {

             if(tim[i]-tim[j]>=abs(x[i]-x[j])+abs(y[i]-y[j]))

             {

                 dp[i]=max(dp[i],dp[j]+);

             }

         }

         ans=max(ans,dp[i]);

     }

 }

 void print()

 {

     cout<<ans<<endl;

 }

 int main()

 {

     read();

     solve();

     print();

 }

巴特西

BZOJ 1207 [HNOI2004]打鼹鼠：dp【类似最长上升子序列】

最新文章

热门文章