扫描透镜-贪心-动归

题目描述

在N*M的草地上,提莫种了K个蘑菇,蘑菇爆炸的威力极大,兰博不想贸然去闯,而且蘑菇是隐形的.只 有一种叫做扫描透镜的物品可以扫描出隐形的蘑菇,于是他回了一趟战争学院,买了2个扫描透镜,一个 扫描透镜可以扫描出(3*3)方格中所有的蘑菇,然后兰博就可以清理掉一些隐形的蘑菇. 问:兰博最多可以清理多少个蘑菇? 注意：每个方格被扫描一次只能清除掉一个蘑菇。 输入描述: 第一行三个整数:N,M,K,(1≤N,M≤20,K≤100),N,M代表了草地的大小; 接下来K行,每行两个整数x,y(1≤x≤N,1≤y≤M).代表(x,y)处提莫种了一个蘑菇. 一个方格可以种无穷个蘑菇.

输出描述: 输出一行,在这一行输出一个整数,代表兰博最多可以清理多少个蘑菇. 样例输入

14 8 47 11 5 7 2 1 1 12 4 8 7 13 2 6 5 4 5 1 5 5 3 4 1 5 3 7 8 3 3 4 3 3 7 5 2 10 8 11 7 1 7 11 6 12 8 13 2 2 8 10 2 12 4 10 2 1 5 5 8 12 5 10 8 4 5 1 6 8 6 10 3 4 8 8 2 3 4 14 8 4 8 12 8 11 6 12 1 10 3 5 2 8 1 6 6

样例输出

9

http://www.nowcoder.com/practice/6a219d196df44d3abd82fbadb1a62c3f?tpId=49&tqId=29331&rp=4&ru=%2Fta%2F2016test&qru=%2Fta%2F2016test%2Fquestion-ranking

---

注意题目的描述

ac代码如下，待优化

#include <cstdio> #include <cstdlib> #include <vector> #include <algorithm> #include <iostream> using namespace std; /* mp是引用，每次扫描要修改 */ int func(vector<vector<int>> &mp, int n, int m) { vector<int> dp(n); int maxVal,posx,posy; // 第一行的值 即 j = 1 for (int i = 1; i <= 3; i++) { for (int j = 1; j <= 3; j++) { if (mp[i][j] > 0) dp[1] ++; } } maxVal = dp[1]; posx = 1; posy = 1; for (int i = 2; i <= n - 2; i++) { int tmp1 = 0; int tmp2 = 0; for (int j = 1; j <= 3; j++) { if (mp[i - 1][j] > 0) // 前面的列 tmp1++; if (mp[i + 2][j] > 0) //后面的列 tmp2++; } dp[i] = dp[i - 1] - tmp1 + tmp2; if (dp[i] > maxVal) maxVal = dp[i]; } // 计算依次计算后面每一行的值 即 j = 2, 3 , ... m - 2 , 每一行依赖于上一行dp for (int j = 2; j <= m - 2; j++) { for (int i = 1; i <= n - 2; i++) { // j i 的 3*3方格内 int tmp1 = 0; int tmp2 = 0; for (int ii = i; ii <= i + 2; ii++) { if (mp[ii][j-1] > 0) // 前面的行 tmp1++; if (mp[ii][j+2] > 0) //后面的行 tmp2++; } dp[i] = dp[i] - tmp1 + tmp2; // 更新dp[i] if (dp[i] > maxVal) { maxVal = dp[i]; posx = i; posy = j; } }// end for i }// end for j // 得到了最大的方格后，蘑菇数减去1，等待下一个蘑菇 for (int i = posx; i <= posx+2; i++) { for (int j = posy; j <= posy+2; j++) { if (mp[i][j] > 0) mp[i][j] --; } } return maxVal; } int main() { //freopen("in.txt", "r", stdin); int n, m, k; while (scanf("%d%d%d", &n, &m, &k) != EOF) { if (k <= 0) { printf("0\n"); continue; } if (n < 3) n = 3; if (m < 3) m = 3; vector<vector<int>> mp(n+1, vector<int>(m+1, 0)); int x, y; for(int i = 0; i < k; i++) { scanf("%d%d", &x, &y); if (x >= 1 && x <= n && y >= 1 && y <= m) mp[x][y] ++; } int rs = 0; rs += func(mp,n,m); rs += func(mp, n, m); printf("%d\n", rs); } return 0; }