my code:

/*
?* 2029.cpp
?*
?*? Created on: 2011-7-6
?*????? Author:
?*/

#include <iostream>
#include <cstring>
using namespace std;

const int MAXN = 100 + 5;
bool tree[MAXN][MAXN] = {};???　　 //坐標上是否有樹
int d[MAXN][MAXN] = {};???　　　　 //一維矩陣上的樹的總數（坐標表示1*1元）
int ans[MAXN][MAXN] = {};??? 　　　//s * t 矩陣上的樹的總數（坐標表示1*1元）
int imax = -1;

int main(){
??? int n, w, h, s, t;
??? while(cin >> n){
??? ??? if(n == 0)
??? ??? ??? break;

??? ??? cin >> w >> h;

??? ??? memset(tree, 0, sizeof(bool) * MAXN * MAXN);

??? ??? int tmp_x, tmp_y;
??? ??? for(int i=0; i<n; i++){
??? ??? ??? cin >> tmp_x >> tmp_y;
??? ??? ??? tree[tmp_x][tmp_y] = 1;
??? ??? }

??? ??? cin >> s >> t;



??? ??? memset(d, 0, sizeof(int) * MAXN * MAXN);
??? ??? memset(ans, 0, sizeof(int) * MAXN * MAXN);
??? ??? imax = -1;


??? ??? for(int i=1; i<=w-s+1; i++){
??? ??? ??? for(int j=1; j<=h; j++){
??? ??? ??? ??? for(int k=0; k<s; k++){
??? ??? ??? ??? ??? d[i][j] += tree[i+k][j];
??? ??? ??? ??? }
??? ??? ??? }
??? ??? }

??? ??? for(int i=1; i<=w-s+1; i++){
??? ??? ??? for(int j=1; j<=h-t+1; j++){
??? ??? ??? ??? for(int k=0; k<t; k++){
??? ??? ??? ??? ??? ans[i][j] += d[i][j+k];
??? ??? ??? ??? }

??? ??? ??? ??? if(imax < ans[i][j])
??? ??? ??? ??? ??? imax = ans[i][j];
??? ??? ??? }
??? ??? }


??? ??? cout << imax << endl;
??? }


??? return 0;
}

其他code：【轉】

1）　　DP

思路：基礎DP。預處理存所有矩形[(1,1)(i,j)]里面的樹的總數量。枚舉小矩形的位置，然后DP，狀態轉移方程：ans = max(dp[i][j] - dp[ii-1][j] - dp[i][jj-1] + dp[ii-1][jj-1])。也可以用樹狀數組，但是沒這個必要，樹狀數組能修改點的情況，這里每個點的情況是固定的。

?

源代碼：(312K, 16MS)

#include<iostream>
#define max(a,b) ((a)>(b)?(a):(b))
using namespace std;
const int MAX = 105;

?

int map[MAX][MAX];
int dp[MAX][MAX];

?

int main(){
??? int n, i, j, ii, jj;
??? int W, H, w, h;
??? while(cin >> n && n){
??????? memset(map, 0, sizeof(map));
??????? memset(dp, 0, sizeof(dp));
??????? cin >> W >> H;
??????? while(n --){
??????????? int x, y;
??????????? cin >> x >> y;
??????????? map[y][x] = 1;
??????? }
??????? cin >> w >> h;
??????? for(i = 1; i <= H; i ++)
??????????? for(j = 1; j <= W; j ++)
??????????????? dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + map[i][j];
??????? int ans = 0;
??????? for(i = 1; i <= H; i ++)
??????????? for(j = 1; j <= W; j ++){
??????????????? ii = i - h + 1;
??????????????? jj = j - w + 1;
??????????????? if(ii < 1 || jj < 1) continue;
??????????????? ans = max(ans, dp[i][j] - dp[ii-1][j] - dp[i][jj-1] + dp[ii-1][jj-1]);
??????????? }
??????? cout << ans << endl;
??? }
??? return 0;
}

2）　　樹狀數組

感覺這樣用樹狀數組，也有點小暴力～～

#include<iostream>
#include<cstring>
using namespace std;
const int N = 105;
int c[N][N];
int lowbit(int x)
{
return x&(-x);
}
void? update(int x, int y)
{
for(int i = x; i < N; i+=lowbit(i))
for(int j = y; j < N; j+=lowbit(j))
c[i][j]++;
}
int sum(int x, int y)
{
int ans = 0;
for(int i = x; i > 0; i -= lowbit(i))
for(int j = y; j > 0; j -= lowbit(j))
ans += c[i][j];
return ans;
}
void init()
{
memset(c,0,sizeof(c));
}
int main()
{
??? int n,w,h,x,y;
??? while(cin>>n && n)
??? {
??? ??? init();
??? ??? cin>>w>>h;
??? ??? for(int i = 0; i < n; i++)
??? ??? {
??? ??? ??? cin>>x>>y;
??? ??? ??? update(x,y);
??? ??? }
??? ??? cin>>x>>y;
??? ??? int ans = 0;
??? ??? for(int i = 1; i <= w-x+1; i++)
??? ??? for(int j = 1; j <= h-y+1; j++)
??? ??? {
??? ??? ??? ans = max(ans,sum(i+x-1,j+y-1)+sum(i-1,j-1)-sum(i+x-1,j-1)-sum(i-1,j+y-1));
??? ??? }
??? cout<<ans<<endl;
??? }
??? return 0;
}

總結

以上是生活随笔為你收集整理的poj-2029 Get Many Persimmon Trees的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。