poj 2029 Get Many Persimmon Trees (dp)

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题目链接

又是一道完全自己想出来的dp题。

题意：一个w*h的图中，有n个点，给一个s*t的圈，求这个圈能圈的最多的点

分析：d[i][j]代表i行j列到第一行第一列的这个方框内有多少个点，然后枚举圈的右下角的点，

计算在圈的范围的点的方法为

d[i][j]-d[i][j-s]-d[i-t][j]+d[i-t][j-s]。

 #include <iostream>

 #include <cstring>

 #include <cstdio>

 #include <algorithm>

 #define LL long long

 using namespace std;

 const int maxn =  + ;

 int d[][], G[][];

 int n, w, h, s, t;

 int main()

 {

     int i, j, x, y, sum, ans;

     while(~scanf("%d", &n) && n)

     {

        ans = ;

        memset(d, , sizeof(d));

        memset(G, , sizeof(G));

        scanf("%d%d", &w, &h);

        for(i = ; i <= n; i++)

        {

            scanf("%d%d", &x, &y);

            G[y][x] = ;

        }

        scanf("%d%d", &s, &t);

        for(i = ; i <= h; i++)

        {

            sum = ;

            for(j = ; j <= w; j++)

            {

                if(G[i][j] == )

                sum++;

                d[i][j] = d[i-][j] + sum;

            }

        }

        for(i = t; i <= h; i++)

        for(j = s; j <= w; j++)

        {

            ans = max(ans, d[i][j]-d[i][j-s]-d[i-t][j]+d[i-t][j-s]);

        }

        printf("%d\n", ans);

     }

     return ;

 }