NPSC補完計劃

登入註冊帳號.

請輸入帳號, 密碼以及預計登入時間
進階搜尋  

最新消息:

歡迎光臨NPSC補完計劃

+ NPSC補完計劃 » NPSC國中組 » NPSC2004國中組決賽
 NPSC 2004國決 A 彩紙片片

作者 主題: NPSC 2004國決 A 彩紙片片  (閱讀 494 次)

rscpp

  • 中級會員
  • ***
  • 文章數: 60
    • 檢視個人資料
NPSC 2004國決 A 彩紙片片
« 於: 五月 07, 2015, 08:49:07 pm »

代碼: [選擇]
// npsc04-j2a (2004國中決 題目 A 彩紙片片)
// n 張彩紙,依其位置在公告欄的每1小格計數,所需執行的次數粗估如下
// t<=15, n<=1000, 每張海報<= 100x100, ( 15 x (清公告欄(1000x1000)) + (貼彩紙(1000x100x100)) ) <= 1.65 * 10^8
// 要看測資,不曉得會不會逾時, 但我只想得到這個方法,不曉得有沒有更快的方法?
#include <iostream>
#include <cstring>
using namespace std;
const int maxn=1010;
int bd[maxn][maxn];
int main()
{
  int i,j,A,B,t;
cin >> t;
while(t--)
{
cin >> A >> B;
for(i=A;i>=0;--i)
   for(j=B;j>=0;--j)
    bd[i][j]=0;
int x,y,w,h,n, m=0;
cin >> n;
while(n--)
      {
cin >> x >> y >> w >> h;
for(i=x+w-1; i>=x; --i)
for(j=y+h-1; j>=y; --j)
if( ++(bd[i][j]) > m ) m = bd[i][j];
}
cout << m << endl;   
}

  return 0;
}
/*
範例輸入:
2
10 10
5
1 1 2 3
2 4 3 5
1 3 2 4
9 9 1 1
0 0 1 1
11 11
7
3 1 4 7
1 2 9 3
2 3 3 3
6 3 3 4
3 7 3 2
6 0 2 4
6 3 1 5
範例輸出:
2
5
*/

記錄
+ NPSC補完計劃 » NPSC國中組 » NPSC2004國中組決賽
 NPSC 2004國決 A 彩紙片片