程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> hihocoder #1042 : 跑馬圈地

hihocoder #1042 : 跑馬圈地

編輯:C++入門知識

hihocoder #1042 : 跑馬圈地


 

時間限制:10000ms 單點時限:1000ms 內存限制:256MB

描述

一覺醒來,小Hi穿越回了古代!由於破敵有功,大汗賞賜小Hi可以在敵人的草原上跑馬圈地:一天之內騎馬圍住的草原以後就是小Hi的牧場。但是令小Hi頭疼的是,敵人的草原上有一塊臭水塘。小Hi不能騎馬走進臭水塘裡,並且即使小Hi的騎馬路徑圍住了臭水塘,小Hi的牛馬也不能在臭水塘裡放牧。

 

為了更科學地圈地,小Hi對這個問題進行了簡化和抽象:(1)敵人的草原是一塊n×m的方格矩陣,(2)騎馬的路徑是沿著方格邊緣的一段封閉折線,(3)臭水塘是矩陣中的一塊矩形,(4)騎馬的路徑周長不超過L。小Hi想知道自己最大能圈住多大面積的草原(臭水塘的面積不計入在內)。

\

如圖所示:圖1是一條合法的路徑;圖2也是一條合法的路徑,但是圈住的草原面積為0;圖3不是合法的路徑,因為沒有封閉;圖4也不是合法的路徑,因為穿過了水塘。

輸入

第一行3個整數:n, m, L (1 <= n, m <= 100, 1 <= L <= 400)

第二行4個整數:l, r, t, b (0 <= l < r <= m, 0 <= t < b <= n)表示水塘的左、右、上、下邊界坐標。

輸出

小Hi最大能圈住的面積

樣例輸入
4 4 8
1 3 1 3
樣例輸出
3

 

很顯然L越大覆蓋的面積就越大,所以這題應該是周長取L時枚舉所有的面積。

主要是考慮一下三種情況:

1.圈地與水塘沒有重疊部分

2.水塘的一個頂點在圈地內

3.水塘的四個頂點都在圈地內

 

可以通過坐標變換,把水塘都變成位於草原右上角的情況。

根據水塘中心的坐標來判斷水塘是位於左上、右上、左下還是右下。

 

對於水塘坐標的轉換

 

int l1, r1, t1, b1;
	if (l + r <= m &&t + b <= n)   //左下角
	{
		l1 = m - r;
		r1 = m - l;
		t1 = n - b;
		b1 = n - t;
	}
	else if (l + r >= m &&t + b <= n)  //右下角
	{
		l1 = l;
		r1 = r;
		t1 = n - b;
		b1 = n - t;
	}
	else if (l + r <= m &&t + b >= n)  //左上角
	{
		l1 = m - r;
		r1 = m - l;
		t1 = t;
		b1 = b;
	}

可以簡化成:

 

 

int l1, r1, t1, b1;
	l1 = l;
	r1 = r;
	t1 = t;
	b1 = b;
	if (l + r <= m)   
	{
		l1 = m - r;
		r1 = m - l;
	}
	if (t + b <= n)
	{
		t1 = n - b;
		b1 = n - t;
	}

完整程序如下:

 

 

#include 
using namespace std;

int main()
{
	int n, m, L, l, r, t, b;
	cin >> n >> m >> L;
	cin >> l >> r >> b >> t;
	if (L >= 2 * (m + n))
	{
		cout << m*n - (r - l)*(t - b) << endl;
		return 0;
	}
	int l1, r1, t1, b1;
	l1 = l;
	r1 = r;
	t1 = t;
	b1 = b;
	if (l + r <= m)   
	{
		l1 = m - r;
		r1 = m - l;
	}
	if (t + b <= n)
	{
		t1 = n - b;
		b1 = n - t;
	}
	int ans = 0;
	for (int i = 1; i < L / 2 && i <= m; i++)
	{
		for (int j = 1; j <= L / 2 - i&&j <= n; j++)
		{
			if (i <= l1 || j <= b1)
				ans = ans >i*j ? ans : i*j;
			else if (i > l1 && i <= r1 && j > b1 && j <= t1)
				ans = ans > i*j - (i - l1)*(j - b1) ? ans : i*j - (i - l1)*(j - b1);
			else if (i >= r1&&j >= t1)
				ans = ans > i*j - (r - l)*(t - b) ? ans : i*j - (r - l)*(t - b);
			else
				continue;
		}
	}

	cout << ans << endl;
	system(pause);

	return 0;
}


 

(づ ̄ 3 ̄)づ

 

 

 

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved