POJ 2029 Get Many Persimmon Trees

제목: 평면에 주어진 점들이 있는데, 주어진 크기의 직사각형 (회전할 수 없음) 으로 가장 많은 점을 테두리에 두다.
사고방식: 모든 왼쪽 위의 정점이 (1,1)이고 오른쪽 아래의 정점이 (x,y)인 직사각형 안의 점의 수량을 미리 처리하여 dp[x][y]로 저장한다.나도 이런 방법이 dp인지 아닌지 모르겠어...어쨌든 문제는 매우 까다롭다.

 1 #include<stdio.h>

 2 #include<string.h>

 3 #include<algorithm>

 4 using namespace std;

 5 int dp[110][110];

 6 int main()

 7 {

 8     //freopen("data.in", "r", stdin);

 9     int n;

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

11     {

12         int w, h;

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

14         memset(dp, 0, sizeof(dp));

15         while (n--)

16         {

17             int x, y;

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

19             dp[x][y] = 1;

20         }

21         for (int i = 1; i <= w; i++)

22             for (int j = 1; j <= h; j++)

23                 dp[i][j] += dp[i-1][j] -dp[i-1][j-1] + dp[i][j-1];

24         int s, t;

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

26         int res = 0;

27         for (int i = s; i <= w; i++)

28             for (int j = t; j <= h; j++)

29                 res = max(res, dp[i][j] - dp[i-s][j] + dp[i-s][j-t] - dp[i][j-t]);

30         printf("%d
", res);

31     }

32     return 0;

33 }