亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

[ACM_ZJUT_1063]Lily's Puzzle

系統 2381 0

Lily's puzzle

Time Limit:1000MS Memory Limit:32768K

Description
最近lily的好朋友Kingly在農場里干活,農場里種了很多樹,Kingly的任務就是:給定樹的位置,然后到農場里清點樹的棵數,由于他比較死板,只會一棵棵去數,所以他的工資比別人少。而lily就提醒他用計算機,因為這是計算速度最快的東東!同時lily又想到了一個問題:如果給定一個區域的尺寸,怎么樣才能數出這個范圍內的樹最多?
舉個例子,在下圖中,農場是一個寬為10長為8的矩形。


[ACM_ZJUT_1063]Lily's Puzzle


每個(*) 代表一棵樹。 如果給定區域的一邊為4另一邊為3的,那么顯然是左上方的小矩形區域中的樹最多,是5棵。 你的任務就是解決上述的問題!

Input
輸入有多組測試數據,每組數據的格式如下: N W H x1 y1 x2 y2 ... xN yN S T N是樹的總數(0<N<=500) , W 和 H 分別是農場的寬和長。 你可以假設W 和 H 是正整數他們的值不大于100。 每個i (1 <= i <= N), xi 和 yi 是第i棵樹的坐標 。 你可以假設 1 <= xi <= W 和 1 <= yi <= H, 沒有兩棵樹的位置是相同的,但是你不能假設樹是以某種順序排列好的。最后 S 和 T 是給定區域的兩條邊(均為整數),你可以假設 1 <= S ,T <= min(W,H)。 唯一的一個0代表輸入結束。

Output
對于每組數據,請輸出一個整數,代表給定區域中最多幾棵樹!

Sample Input
16
10 8
2 2
2 5
2 7
3 3
3 8
4 2
4 5
4 8
6 4
6 7
7 5
7 8
8 1
8 4
9 6
10 3
4 3
8
6 4
1 2
2 1
2 4
3 4
4 2
5 3
6 1
6 2
3 2
0

Sample Output
5
3

Source
ZJUT1063

窮舉(TLE):

    #include<stdio.h>
#include<memory>

int a[101][101];
int b[101][101];

int Solve(int w, int h, int s, int t){
	int row, col, i, j, k, max;
	for(i = 1; i <= t; ++i){
		for(j = 1; j <= s; ++j){
			b[1][1] += a[i][j];
		}
	}
	max = b[1][1];
	for(i = 2; i <= h - t + 1; ++i){
		b[i][1] = b[i - 1][1];
		for(j = 1; j <= s; ++j){
			b[i][1] += a[i - 1 + t][j] - a[i - 1][j];
		}
		if(max < b[i][1])
			max = b[i][1];
	}
	for(k = 2; k <= w - s + 1; ++k){
		b[1][k] = b[1][k - 1];
		for(i = 1; i <= t; ++i){
			b[1][k] += a[i][k - 1 + s] - a[i][k - 1];
		}
		if(max < b[1][k])
			max = b[1][k];
		for(i = 2; i <= h - t + 1; ++i){
			b[i][k] = b[i - 1][k];
			for(j = k; j <= k + s - 1; ++j){
				b[i][k] += a[i - 1 + t][j] - a[i - 1][j];
			}
			if(max < b[i][k])
				max = b[i][k];
		}
	}
	return max;
}

int main(){
	int trees, w, h, s, t, i, j;
	while(scanf("%d", &trees) && trees){
		memset(a, 0, sizeof(a));
		memset(b, 0, sizeof(b));
		scanf("%d%d", &w, &h);
		while(trees--){
			scanf("%d%d", &j, &i);
			a[i][j] = 1;
		}
		scanf("%d%d", &s, &t);
		int max = Solve(w, h, s, t);
		if(s != t){
			memset(b, 0, sizeof(b));
			int tmp = Solve(w, h, t, s);
			if(tmp > max)
				max = tmp;
		}
		printf("%d\n", max);
	}
	return 0;
}
  

      
        超哥 13:51:13
      
      
算法復雜度可以降到O(N* min(S,T)) + O(WH)

你的算法是從格子計數,可以從樹的角度出發,
如先考慮一個 O(N*S*T) + O(WH)復雜度的算法

即b[i][j]是左上角坐標為(i,j)格子所對應 長度為(S*T)矩陣內的樹的個數,
先從樹的個數做循環(輸入中,把樹的坐標全部壓如vector)

每個數最多屬于 S*T個矩陣,如果他屬于b[i][j],則 b[i][j]++;

最后用一個 O(WH)的循環把b[i][j]的最大值找出來。

類似這個思路,可以推出一個更小復雜度的 O(N* min(S,T)) + O(WH)
    

可是又是一個TLE:

    #include<stdio.h>
#include<memory>
#include<vector>
using namespace std;
int a[101][101];

struct T{
	int row, col;
	T(int row, int col):row(row), col(col){}
};

int Solve(vector<T> &v, int w, int h, int s, int t){
	int i, j, max = 0;
	memset(a, 0, sizeof(a));
	for(vector<T>::iterator it = v.begin(); it != v.end(); ++it){
		for(i = (*it).row; i > (*it).row - s && i > 0; --i){
			for(j = (*it).col; j > (*it).col - t && j > 0; --j){
				++a[i][j];
				if(a[i][j] > max)
					max = a[i][j];
			}
		}
	}
	return max;
}

int main(){
	int trees, w, h, s, t, i, j;
	while(scanf("%d", &trees) && trees){
		vector<T> v;
		scanf("%d%d", &w, &h);
		while(trees--){
			scanf("%d%d", &j, &i);
			v.push_back(T(j, i));
		}
		scanf("%d%d", &s, &t);
		int max = Solve(v, w, h, s, t);
		if(s != t){
			int tmp = Solve(v, w, h, t, s);
			if(tmp > max)
				max = tmp;
		}
		printf("%d\n", max);
	}
	return 0;
}
  

很神奇地,把scanf改為cin就通過了(以上兩種方法都可以AC,據說是某些編譯器對于cin會有所優化):

    #include<iostream>
#include<memory>
using namespace std;
int a[101][101];
int b[101][101];

int Solve(int w, int h, int s, int t){
    int row, col, i, j, k, max;
    for(i = 1; i <= t; ++i){
        for(j = 1; j <= s; ++j){
            b[1][1] += a[i][j];
        }
    }
    max = b[1][1];
    for(i = 2; i <= h - t + 1; ++i){
        b[i][1] = b[i - 1][1];
        for(j = 1; j <= s; ++j){
            b[i][1] += a[i - 1 + t][j] - a[i - 1][j];
        }
        if(max < b[i][1])
            max = b[i][1];
    }
    for(k = 2; k <= w - s + 1; ++k){
        b[1][k] = b[1][k - 1];
        for(i = 1; i <= t; ++i){
            b[1][k] += a[i][k - 1 + s] - a[i][k - 1];
        }
        if(max < b[1][k])
            max = b[1][k];
        for(i = 2; i <= h - t + 1; ++i){
            b[i][k] = b[i - 1][k];
            for(j = k; j <= k + s - 1; ++j){
                b[i][k] += a[i - 1 + t][j] - a[i - 1][j];
            }
            if(max < b[i][k])
                max = b[i][k];
        }
    }
    return max;
}

int main(){
    int trees, w, h, s, t, i, j;
    while(cin >>  trees && trees){
        memset(a, 0, sizeof(a));
        memset(b, 0, sizeof(b));
        cin >> w >> h;
        while(trees--){
            cin >> j >> i;
            a[i][j] = 1;
        }
        cin >> s >> t;
        int max = Solve(w, h, s, t);
        if(s != t){
            memset(b, 0, sizeof(b));
            int tmp = Solve(w, h, t, s);
            if(tmp > max)
                max = tmp;
        }
        cout << max << endl;
    }
    return 0;
}
  


    
      #include<iostream>
#include<memory>
#include<vector>
using namespace std;
int a[101][101];

struct T{
    int row, col;
    T(int row, int col):row(row), col(col){}
};

int Solve(vector<T> &v, int w, int h, int s, int t){
    int i, j, max = 0;
    memset(a, 0, sizeof(a));
    for(vector<T>::iterator it = v.begin(); it != v.end(); ++it){
        for(i = (*it).row; i > (*it).row - s && i > 0; --i){
            for(j = (*it).col; j > (*it).col - t && j > 0; --j){
                ++a[i][j];
                if(a[i][j] > max)
                    max = a[i][j];
            }
        }
    }
    return max;
}

int main(){
    int trees, w, h, s, t, i, j;
    while(cin >> trees && trees){
        vector<T> v;
        cin >> w >> h;
        while(trees--){
            cin >> j >> i;
            v.push_back(T(j, i));
        }
        cin >> s >> t;
        int max = Solve(v, w, h, s, t);
        if(s != t){
            int tmp = Solve(v, w, h, t, s);
            if(tmp > max)
                max = tmp;
        }
        cout << max << endl;
    }
    return 0;
}
    
  

志的代碼,思路是遍歷所有位置,每個位置從vector中找到范圍內的樹,每找到一個,樹的數目加1,最終比較得出結果:

    #include<memory>
#include<iostream>
#include<vector>
using namespace std;
struct T{
    int row, col;
    T(int row, int col):row(row), col(col){}
}; 

int Solve(int i,int j,int s,int t,vector<T> v)
{
    int suma=0;
    int sumb=0;
    for(int k=0;k<v.size();k++)
    {
        if(v[k].row<i+t && v[k].row>=i && v[k].col<j+s && v[k].col>=j)
            suma++;
        if(v[k].row<i+s && v[k].row>=i && v[k].col<j+t && v[k].col>=j)
            sumb++;
    }
    if(suma>=sumb)
        return suma;
    else
        return sumb;
}
int main()
{
    int trees, w, h, s, t, i, j;
    while(cin>>trees && trees)
    {
        vector<T> v;
        cin >> w >> h;
        while(trees--)
        {
            cin >> j >> i;
            v.push_back(T(j, i));
        }
        cin >> s >> t;
        int maxtree=0,temptree=0;
        for(int i=0;i<=w;i++)
        {
            for(int j=0;j<=h;j++)
            {
                temptree=Solve(i,j,s,t,v);
                if(temptree>maxtree)
                    maxtree=temptree;
            }
        }
        cout << maxtree << endl;
    }
    return 0;
}
  

三種方法運行結果如下:

Method Result Time(MS) Memory(K) Length Language
窮舉 Accepted 31 212 1197 G++
遍歷樹 Accepted 10 252 1114 G++
遍歷位置 Accepted 13 288 1611 G++

可以看出遍歷樹更好一些,畢竟樹的數量要遠小于位置數量。

    
      
      
    
    

=======================簽 名 檔=======================
原文地址(我的博客): http://www.clanfei.com/2012/04/790.html
歡迎訪問交流,至于我為什么要多弄一個博客,因為我熱愛前端,熱愛網頁,我更希望有一個更加自由、真正屬于我自己的小站,或許并不是那么有名氣,但至少能夠讓我為了它而加倍努力。。
=======================簽 名 檔=======================




[ACM_ZJUT_1063]Lily's Puzzle


更多文章、技術交流、商務合作、聯系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號聯系: 360901061

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。

【本文對您有幫助就好】

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長會非常 感謝您的哦!!!

發表我的評論
最新評論 總共0條評論
主站蜘蛛池模板: 四虎精品免费永久在线 | 中文字幕免费在线观看 | 高清欧美一区二区三区 | 国内精品视频在线播放一区 | 中文字幕人成乱码第一页 | 亚洲综合激情六月婷婷在线观看 | 国产美女精品在线观看 | 久久国产精品亚洲综合 | 精品中文字幕一区二区三区四区 | 黄页网址在线免费观看 | 九九久久国产精品 | 人人操天天射 | 夜色福利一区二区三区 | 超级乱淫视频aⅴ播放视频 超级乱淫视频播放日韩 | 99 久久99久久精品免观看 | 欧美人与动人物a级网站 | 91av中文| 九九热精品视频在线播放 | 狠狠干夜夜草 | 中文字幕日本精品一区二区三区 | 美女久久久久久 | 日本免费在线视频 | 日本高清有码 | 老妇色 | 人人爱人人做 | 国产特级毛片aaaaaa | 久在线视频 | 精品91在线 | 久久久999久久久精品 | 大陆一级毛片免费视频观看 | 日韩亚洲精品不卡在线 | 奇米777777| 一级骚片超级骚在线观看 | 奇米第四色在线观看 | 欧美成人一区二区三区不卡视频 | 一级片在线视频 | 最新仑乱免费视频 | 亚洲国产精品综合一区在线 | 四虎影院在线免费观看 | 五月一区二区久久综合天堂 | 老师在办公室被躁到白浆 |