A. C語言 演算法題 (自己改過的)
其實這個題不難，就是要自己在草稿紙上畫一下，找出數列的遞推公式，下面是我編的，只輸入前20個月的兔子數，樓主想要輸出更多隻要將M的值改下就行了，在VC6.0編譯通過，有不明白的隨時問我!
#include<stdio.h>
#define M 20
void main()
{
int N;
int a[M];
int i;
printf("請輸入第幾個月開始生小兔子：\n");
scanf("%d",&N);
for(i=0;i<N-1;i++)
a[i]=1; /*前N-1個月兔子總數只有1隻*/
for(i=N-1;i<M;i++)
a[i]=a[i-N+1]+a[i-1];
printf("兔子數為：\n");
for(i=0;i<M;i++)
{
printf("%5d",a[i]);
if((i+1)%10==0)
printf("\n");/*每10個換行一次*/
}
}
B. 求一個C++中，最大堆(最小堆)編譯，要求時間復雜度為線性
#include<iostream>
#include<vector>
usingnamespacestd;
#defineParent(i)(((i)-1)/2)
#defineLeft(i)(2*(i)+1)
#defineRight(i)(2*(i)+2)
template<typenameT>
voidKeepHeap(vector<T>&Cont,size_tIndex)
{
size_tLargest=Index;
size_tBound=Cont.size();
size_tleft=Left(Index);
size_tright=Right(Index);
if(left<=Bound&&Cont[left]>Cont[Index])
{
Largest=left;
}
if(right<=Bound&&Cont[right]>Cont[Largest])
{
Largest=right;
}
if(Largest!=Index)
{
Ttmp=Cont[Largest];
Cont[Largest]=Cont[Index];
Cont[Index]=tmp;
}
else
{
return;
}
KeepHeap(Cont,Largest);
}
template<typenameT>
voidMakeHeap(vector<T>&Cont)
{
size_tMid=Cont.size()/2;
for(inti=Mid-1;i>=0;--i)
{
KeepHeap(Cont,i);
}
}
寫了個大概 能運行 但是肯定有紕漏 只是個玩具而已 不具有什麼強度 LZ自己修改
不過復雜度應該是線性的 要證明復雜度為線性也是可以的
C. 數據結構題目，跪求大神，好心人，相助啊啊啊 啊 趴求
1. D
2. A
3. A
4. C
5. C
6. B
7. D
8. C
9. D
10. A
11. D
12. A
13. C
14. A
15. A
16. B
D. 以前玩過一個東西，有幾個大學出的關於演算法的題目，可以在線編譯的，好像叫asm什麼的，希望知道的能夠告訴
http://www.vckbase.com/sourcecode/algorithms/
不知道你說的是什麼網站不過這個站點上有幾個演算法很不錯，也有源碼，可以看看。另外有找到你說的網站的話，可以給我也推薦下，大家一起學習。嘿嘿
希望我的回答可以幫到你。
E. c++ 最短作業時間進程調度演算法的變數定義問題
定義數組時，數組大小必須是編譯時期就能計算出來的值。這一點很好理解，否則編譯器不知道要分配多少空間。
如果「數組」大小編譯時期算不出來（比如要用戶scanf），那麼應該用動態內存分配，類似這個樣子：
#include <stdlib.h>
int main()
{
int n;
scanf("%d",&n);
struct JobStruct *Job;
Job=(struct JobStruct *)malloc(n * sizeof(struct JobStruct));
...
}
F. 怎樣求10000000以內的素數，演算法，要在比較短的時間內出結果。
關於素數求解，我在網路知道裡面回復過幾篇，顛來倒去也就這么點知識。
求解200萬以內的所有素數，可以直接用厄拉多塞演算法，詳細情況可以參考該鏈接內我的回答，也就是最佳答案：http://..com/question/94494946.html，將長度修改成200萬是沒問題的，至少VC6上面編譯通過的。
200萬以上的素數，如果單純的求解某個數是否是素數，那麼用厄拉多塞+拉賓米勒+Pollard啟發演算法就可以AC了（參見http://..com/question/88011147.html，也是我自己的回答，所以應該不算是參考資料吧），不過如果要求解所有的素數-_-，好像有些難度哦~反正VC內的數組肯定是支持不了1億的長度的~會崩潰的~
G. 一個超大數（比如10的20次方），求它的約數個數，要求用最快的方法，編譯運行時間不超過一秒！！
重寫寫了個java演算法，效率很理想。
不過long只能支持到10的18次方
運行環境：E8400 + 4G RAM + JDK 1.5 + XP SP3(公司的機子就是牛啊!!!!)
import java.util.ArrayList;
import java.util.List;
public class Submultiple {
public static void main(String args[]){
long start = System.currentTimeMillis();
int[] primeNumAry = new int[64];
get64PrimeNumber(primeNumAry);
long num = 1000000000000000000L;
long orgNum = num;
int facCount = 0;
List<Integer> list = new ArrayList<Integer>();
for(int index = 0, factor = primeNumAry[index]; num != 1; ){
if(num % factor == 0){
facCount++;
num = num /factor;
if(num == 1){
list.add(facCount);
}
continue;
}else{
list.add(facCount);
factor = primeNumAry[++index];
facCount = 0;
}
}
long totalCount = 1L;
for(int item: list){
totalCount *= (item + 1);
}
long end = System.currentTimeMillis();
System.out.println("For number " + orgNum + ", Total " + (end - start)
+ " million seconds for " + totalCount + " submultiples");
}
private static void get64PrimeNumber(int[] primeNumAry) {
Label1: for(int i = 2, count = 0; count < 64; i++){
for(int j = 2; j < i; j++){
if(i % j == 0){
continue Label1;
}
}
primeNumAry[count++] = i;
}
}
}
--------------
For number 1000000000000000000, Total 0 million seconds for 361 submultiples
H. 求解一道演算法設計題
void invert(sequenlist *p)
{
char mid;
int i,j;
i=0;
j=p->last-1;
while(i<j)
{
mid=p->data[i];
p->data[i]=p->data[j];
p->data[j]=mid;
i++;j--;
}
}
I. pascal題目
2003年國家集訓隊論文，王知昆，淺談用極大化思想解決最大子矩形問題
網上有的，O(n²)的復雜度，n，m是5000都能1秒出解
淺談用極大化思想解決最大子矩形問題
福州第三中學 王知昆
【摘要】
本文針對一類近期經常出現的有關最大（或最優）子矩形及相關變形問題，介紹了極大化思想在這類問題中的應用。分析了兩個具有一定通用性的演算法。並通過一些例題講述了這些演算法選擇和使用時的一些技巧。
【關鍵字】 矩形，障礙點，極大子矩形
【正文】
一、 問題
最大子矩形問題：在一個給定的矩形網格中有一些障礙點，要找出網格內部不包含任何障礙點，且邊界與坐標軸平行的最大子矩形。
這是近期經常出現的問題，例如冬令營2002的《奶牛浴場》，就屬於最大子矩形問題。
Winter Camp2002,奶牛浴場
題意簡述：（原題見論文附件）
John要在矩形牛場中建造一個大型浴場，但是這個大型浴場不能包含任何一個奶牛的產奶點，但產奶點可以出在浴場的邊界上。John的牛場和規劃的浴場都是矩形，浴場要完全位於牛場之內，並且浴場的輪廓要與牛場的輪廓平行或者重合。要求所求浴場的面積盡可能大。
參數約定：產奶點的個數S不超過5000,牛場的范圍N×M不超過30000×30000。
二、 定義和說明
首先明確一些概念。
1、 定義有效子矩形為內部不包含任何障礙點且邊界與坐標軸平行的子矩形。如圖所示，第一個是有效子矩形（盡管邊界上有障礙點），第二個不是有效子矩形（因為內部含有障礙點）。
2、 極大有效子矩形：一個有效子矩形，如果不存在包含它且比它大的有效子矩形，就稱這個有效子矩形為極大有效子矩形。（為了敘述方便，以下稱為極大子矩形）
3、 定義最大有效子矩形為所有有效子矩形中最大的一個（或多個）。以下簡稱為最大子矩形。
三、 極大化思想
【定理1】在一個有障礙點的矩形中的最大子矩形一定是一個極大子矩形。
證明：如果最大子矩形A不是一個極大子矩形，那麼根據極大子矩形的定義，存在一個包含A且比A更大的有效子矩形，這與「A是最大子矩形」矛盾，所以【定理1】成立。
四、 從問題的特徵入手，得到兩種常用的演算法
定理1雖然很顯然，但卻是很重要的。根據定理1，我們可以得到這樣一個解題思路：通過枚舉所有的極大子矩形，就可以找到最大子矩形。下面根據這個思路來設計演算法。
約定：為了敘述方便，設整個矩形的大小為n×m，其中障礙點個數為s。
演算法1
演算法的思路是通過枚舉所有的極大子矩形找出最大子矩形。根據這個思路可以發現，如果演算法中有一次枚舉的子矩形不是有效子矩形、或者不是極大子矩形，那麼可以肯定這個演算法做了「無用功」，這也就是需要優化的地方。怎樣保證每次枚舉的都是極大子矩形呢，我們先從極大子矩形的特徵入手。
【定理2】：一個極大子矩形的四條邊一定都不能向外擴展。更進一步地說，一個有效子矩形是極大子矩形的充要條件是這個子矩形的每條邊要麼覆蓋了一個障礙點，要麼與整個矩形的邊界重合。
定理2的正確性很顯然，如果一個有效子矩形的某一條邊既沒有覆蓋一個障礙點，又沒有與整個矩形的邊界重合，那麼肯定存在一個包含它的有效子矩形。根據定理2，我們可以得到一個枚舉極大子矩形的演算法。為了處理方便，首先在障礙點的集合中加上整個矩形四角上的點。每次枚舉子矩形的上下左右邊界（枚舉覆蓋的障礙點），然後判斷是否合法（內部是否有包含障礙點）。這樣的演算法時間復雜度為O(S5)，顯然太高了。考慮到極大子矩形不能包含障礙點，因此這樣枚舉4個邊界顯然會產生大量的無效子矩形。
考慮只枚舉左右邊界的情況。對於已經確定的左右邊界，可以將所有處在這個邊界內的點按從上到下排序，如圖1中所示，每一格就代表一個有效子矩形。這樣做時間復雜度為O(S3)。由於確保每次得到的矩形都是合法的，所以枚舉量比前一種演算法小了很多。但需要注意的是，這樣做枚舉的子矩形雖然是合法的，然而不一定是極大的。所以這個演算法還有優化的餘地。通過對這個演算法不足之處的優化，我們可以得到一個高效的演算法。
回顧上面的演算法，我們不難發現，所枚舉的矩形的上下邊界都覆蓋了障礙點或者與整個矩形的邊界重合，問題就在於左右邊界上。只有那些左右邊界也覆蓋了障礙點或者與整個矩形的邊界重合的有效子矩形才是我們需要考察的極大子矩形，所以前面的演算法做了不少「無用功」。怎麼減少「無用功」呢，這里介紹一種演算法（演算法1），它可以用在不少此類題目上。
演算法的思路是這樣的，先枚舉極大子矩形的左邊界，然後從左到右依次掃描每一個障礙點，並不斷修改可行的上下邊界，從而枚舉出所有以這個定點為左邊界的極大子矩形。考慮如圖2中的三個點，現在我們要確定所有以1號點為左邊界的極大矩形。先將1號點右邊的點按橫坐標排序。然後按從左到右的順序依次掃描1號點右邊的點，同時記錄下當前的可行的上下邊界。
開始時令當前的上下邊界分別為整個矩形的上下邊界。然後開始掃描。第一次遇到2號點，以2號點作為右邊界，結合當前的上下邊界，就得到一個極大子矩形（如圖3）。同時，由於所求矩形不能包含2號點，且2號點在1號點的下方，所以需要修改當前的下邊界，即以2號點的縱坐標作為新的下邊界。第二次遇到3號點，這時以3號點的橫坐標作為右邊界又可以得到一個滿足性質1的矩形（如圖4）。類似的，需要相應地修改上邊界。以此類推，如果這個點是在當前點（確定左邊界的點）上方，則修改上邊界；如果在下方，則修改下邊界；如果處在同一行，則可中止搜索（因為後面的矩形面積都是0了）。由於已經在障礙點集合中增加了整個矩形右上角和右下角的兩個點，所以不會遺漏右邊界與整個矩形的右邊重合的極大子矩形（如圖5）。需要注意的是，如果掃描到的點不在當前的上下邊界內，那麼就不需要對這個點進行處理。
這樣做是否將所有的極大子矩形都枚舉過了呢？可以發現，這樣做只考慮到了左邊界覆蓋一個點的矩形，因此我們還需要枚舉左邊界與整個矩形的左邊界重合的情況。這還可以分為兩類情況。一種是左邊界與整個舉行的左邊界重合，而右邊界覆蓋了一個障礙點的情況，對於這種情況，可以用類似的方法從右到左掃描每一個點作為右邊界的情況。另一種是左右邊界均與整個矩形的左右邊界重合的情況，對於這類情況我們可以在預處理中完成：先將所有點按縱坐標排序，然後可以得到以相鄰兩個點的縱坐標為上下邊界，左右邊界與整個矩形的左右邊界重合的矩形，顯然這樣的矩形也是極大子矩形，因此也需要被枚舉到。
通過前面兩步，可以枚舉出所有的極大子矩形。演算法1的時間復雜度是O(S2)。這樣，可以解決大多數最大子矩形和相關問題了。
雖然以上的演算法（演算法1）看起來是比較高效的，但也有使用的局限性。可以發現，這個演算法的復雜度只與障礙點的個數s有關。但對於某些問題，s最大有可能達到n×m，當s較大時，這個演算法就未必能滿足時間上的要求了。能否設計出一種依賴於n和m的演算法呢？這樣在演算法1不能奏效的時候我們還有別的選擇。我們再重新從最基本的問題開始研究。
演算法2
首先，根據定理1：最大有效子矩形一定是一個極大子矩形。不過與前一種演算法不同的是，我們不再要求每一次枚舉的一定是極大子矩形而只要求所有的極大子矩形都被枚舉到。看起來這種演算法可能比前一種差，其實不然，因為前一種演算法並不是完美的：雖然每次考察的都是極大子矩形，但它還是做了一定量的「無用功」。可以發現，當障礙點很密集的時候，前一種演算法會做大量沒用的比較工作。要解決這個問題，我們必須跳出前面的思路，重新考慮一個新的演算法。注意到極大子矩形的個數不會超過矩形內單位方格的個數，因此我們有可能找出一種時間復雜度是O(N×M)的演算法。
定義：
有效豎線：除了兩個端點外，不覆蓋任何障礙點的豎直線段。
懸線：上端點覆蓋了一個障礙點或達到整個矩形上端的有效豎線。如圖所示的三個有效豎線都是懸線。
對於任何一個極大子矩形，它的上邊界上要麼有一個障礙點，要麼和整個矩形的上邊界重合。那麼如果把一個極大子矩形按x坐標不同切割成多個（實際上是無數個）與y軸垂直的線段，則其中一定存在一條懸線。而且一條懸線通過盡可能地向左右移動恰好能得到一個子矩形（未必是極大子矩形，但只可能向下擴展）。通過以上的分析，我們可以得到一個重要的定理。
【定理3】：如果將一個懸線向左右兩個方向盡可能移動所得到的有效子矩形稱為這個懸線所對應的子矩形，那麼所有懸線所對應的有效子矩形的集合一定包含了所有極大子矩形的集合。
定理3中的「盡可能」移動指的是移動到一個障礙點或者矩形邊界的位置。
根據【定理3】可以發現，通過枚舉所有的懸線，就可以枚舉出所有的極大子矩形。由於每個懸線都與它底部的那個點一一對應，所以懸線的個數＝(n-1)×m（以矩形中除了頂部的點以外的每個點為底部，都可以得到一個懸線，且沒有遺漏）。如果能做到對每個懸線的操作時間都為O(1)，那麼整個演算法的復雜度就是O(NM)。這樣，我們看到了解決問題的希望。
現在的問題是，怎樣在O(1)的時間內完成對每個懸線的操作。我們知道，每個極大子矩形都可以通過一個懸線左右平移得到。所以，對於每個確定了底部的懸線，我們需要知道有關於它的三個量：頂部、左右最多能移動到的位置。對於底部為(i,j)的懸線，設它的高為hight[i,j],左右最多能移動到的位置為left[i,j],right[i,j]。為了充分利用以前得到的信息，我們將這三個函數用遞推的形式給出。
對於以點(i,j)為底部的懸線：
如果點(i－1,j)為障礙點，那麼，顯然以(i,j)為底的懸線高度為1，而且左右均可以移動到整個矩形的左右邊界，即
如果點(i－1,j)不是障礙點，那麼，以(i,j)為底的懸線就等於以(i-1,j)為底的懸線＋點(i,j)到點(i-1,j)的線段。因此，height[i,j]=height[i-1,j]+1。比較麻煩的是左右邊界，先考慮left[i,j]。如下圖所示，(i,j)對應的懸線左右能移動的位置要在(i-1,j)的基礎上變化。
即left[i,j]=max
right[i,j]的求法類似。綜合起來，可以得到這三個參數的遞推式：
這樣做充分利用了以前得到的信息，使每個懸線的處理時間復雜度為O(1)。對於以點(i,j)為底的懸線對應的子矩形，它的面積為(right[i,j]-left[i,j])*height[i,j]。
這樣最後問題的解就是：
Result＝
max
整個演算法的時間復雜度為O(NM)，空間復雜度是O(NM)。
兩個演算法的對比：
以上說了兩種具有一定通用性的處理演算法，時間復雜度分別為O(S2)和O(NM)。兩種演算法分別適用於不同的情況。從時間復雜度上來看，第一種演算法對於障礙點稀疏的情況比較有效，第二種演算法則與障礙點個數的多少沒有直接的關系（當然，障礙點較少時可以通過對障礙點坐標的離散化來減小處理矩形的面積，不過這樣比較麻煩，不如第一種演算法好），適用於障礙點密集的情況。
五、 例題
將前面提出的兩種演算法運用於具體的問題。
1、 Winter Camp2002,奶牛浴場
分析：
題目的數學模型就是給出一個矩形和矩形中的一些障礙點，要求出矩形內的最大有效子矩形。這正是我們前面所討論的最大子矩形問題，因此前兩種演算法都適用於這個問題。
下面分析兩種演算法運用在本題上的優略：
對於第一種演算法，不用加任何的修改就可以直接應用在這道題上，時間復雜度為O(S2)，S為障礙點個數；空間復雜度為O(S)。
對於第二種演算法，需要先做一定的預處理。由於第二種演算法復雜度與牛場的面積有關，而題目中牛場的面積很大（30000×30000），因此需要對數據進行離散化處理。離散化後矩形的大小降為S×S，所以時間復雜度為O(S2)，空間復雜度為O(S)。說明：需要注意的是，為了保證演算法能正確執行，在離散化的時候需要加上S個點，因此實際需要的時間和空間較大，而且編程較復雜。
從以上的分析來看，無論從時空效率還是編程復雜度的角度來看，這道題採用第一種演算法都更優秀。
2、 OIBH模擬賽1,提高組，Candy
題意簡述：（原題見論文附件）
一個被分為 n*m 個格子的糖果盒，第 i 行第 j 列位置的格子裡面有 a [i,j] 顆糖。但糖果盒的一些格子被老鼠洗劫。現在需要盡快從這個糖果盒裡面切割出一個矩形糖果盒，新的糖果盒不能有洞，並且希望保留在新糖果盒內的糖的總數盡量多。
參數約定：1 ≤ n，m ≤ 1000
分析
首先需要注意的是：本題的模型是一個矩陣，而不是矩形。在矩陣的情況下，由於點的個數是有限的，所以又產生了一個新的問題：最大權值子矩陣。
定義：
有效子矩陣為內部不包含任何障礙點的子矩形。與有效子矩形不同，有效子矩陣地邊界上也不能包含障礙點。
有效子矩陣的權值（只有有效子矩形才有權值）為這個子矩陣包含的所有點的權值和。
最大權值有效子矩陣為所有有效子矩陣中權值最大的一個。以下簡稱為最大權值子矩陣。
本題的數學模型就是正權值條件下的最大權值子矩陣問題。再一次利用極大化思想，因為矩陣中的權值都是正的，所以最大權值子矩陣一定是一個極大子矩陣。所以我們只需要枚舉所有的極大子矩陣，就能從中找到最大權值子矩陣。同樣，兩種演算法只需稍加修改就可以解決本題。下面分析兩種演算法應用在本題上的優略：
對於第一種演算法，由於矩形中障礙點的個數是不確定的，而且最大有可能達到N×M,這樣時間復雜度有可能達到O(N2M2)，空間復雜度為O(NM)。此外，由於矩形與矩陣的不同，所以在處理上會有一些小麻煩。
對於第二種演算法，稍加變換就可以直接使用，時間復雜度為O(NM),空間復雜度為O（NM）。
可以看出，第一種演算法並不適合這道題，因此最好還是採用第二種演算法。
3、 Usaco Training, Section 1.5.4, Big Barn
題意簡述（原題見論文附件）
Farmer John想在他的正方形農場上建一個正方形谷倉。由於農場上有一些樹，而且Farmer John又不想砍這些樹，因此要找出最大的一個不包含任何樹的一塊正方形場地。每棵樹都可以看成一個點。
參數約定：牛場為N×N的，樹的棵數為T。N≤1000,T≤10000。
分析：
這題是矩形上的問題，但要求的是最大子正方形。首先，明確一些概念。
1、 定義有效子正方形為內部不包含任何障礙點的子正方形
2、 定義極大有效子正方形為不能再向外擴展的有效子正方形，一下簡稱極大子正方形
3、 定義最大有效子正方形為所有有效子正方形中最大的一個（或多個），以下簡稱最大子正方形。
本題的模型有一些特殊，要在一個含有一些障礙點的矩形中求最大子正方形。這與前兩題的模型是否有相似之處呢？還是從最大子正方形的本質開始分析。
與前面的情況類似，利用極大化思想，我們可以得到一個定理：
【定理4】：在一個有障礙點的矩形中的最大有效子正方形一定是一個極大有效子正方形。
根據【定理4】,我們只需要枚舉出所有的極大子正方形，就可以從中找出最大子正方形。極大子正方形有什麼特徵呢？所謂極大，就是不能再向外擴展。如果是極大子矩形，那麼不能再向外擴展的充要條件是四條邊上都覆蓋了障礙點（【定理2】）。類似的，我們可以知道，一個有效子正方形是極大子正方形的充要條件是它任何兩條相鄰的邊上都覆蓋了至少一個障礙點。根據這一點，可以得到一個重要的定理。
【定理5】：每一個極大子正方形都至少被一個極大子矩形包含。且這個極大子正方形一定有兩條不相鄰的邊與這個包含它的極大子矩形的邊重合。
根據【定理5】,我們只需要枚舉所有的極大子矩形，並檢查它所包含的極大子正方形（一個極大子矩形包含的極大子正方形都是一樣大的）是否是最大的就可以了。這樣，問題的實質和前面所說的最大子矩形問題是一樣的，同樣的，所採用的演算法也是一樣的。
因為演算法1和演算法2都枚舉出了所有的極大子矩形，因此，演算法1和演算法2都可以用在本題上。具體的處理方法如下：對於每一個枚舉出的極大子矩形，如圖所示，如果它的邊長為a、b，那麼它包含的極大子正方形的邊長即為min(a,b)。
考慮到N和T的大小不同，所以不同的演算法會有不同的效果。下面分析兩種演算法應用在本題上的優略。
對於第一種演算法，時間復雜度為O(T2)，對於第二種演算法，時間復雜度為O(N2)。因為N<T，所以從時間復雜度的角度看，第二種演算法要比第一種演算法好。考慮到兩個演算法的空間復雜度都可以承受，所以選擇第二種演算法較好些。
以下是第一種和第二種演算法編程實現後在USACO Training Program Gateway上的運行時間。可以看出，在數據較大時，演算法2的效率比演算法1高。
演算法1：
Test 1: 0.009375
Test 2: 0.009375
Test 3: 0.009375
Test 4: 0.009375
Test 5: 0.009375
Test 6: 0.009375
Test 7: 0.021875
Test 8: 0.025
Test 9: 0.084375
Test 10: 0.3875
Test 11: 0.525
Test 12: 0.5625
Test 13: 0.690625
Test 14: 0.71875
Test 15: 0.75 演算法2：
Test 1: 0.009375
Test 2: 0.009375
Test 3: 0.009375
Test 4: 0.009375
Test 5: 0.009375
Test 6: 0.00625
Test 7: 0.009375
Test 8: 0.009375
Test 9: 0.0125
Test 10: 0.021875
Test 11: 0.028125
Test 12: 0.03125
Test 13: 0.03125
Test 14: 0.03125
Test 15: 0.034375
以上，利用極大化思想和前面設計的兩個演算法，通過轉換模型，解決了三個具有一定代表性的例題。解題的關鍵就是如何利用極大化思想進行模型轉換和如何選擇演算法。
五、小結
設計演算法要從問題的基本特徵入手，找出解題的突破口。本文介紹了兩種適用於大部分最大子矩形問題及相關變型問題的演算法，它們設計的突破口就是利用了極大化思想，找到了枚舉極大子矩形這種方法。
在效率上，兩種演算法對於不同的情況各有千秋。一個是針對障礙點來設計的，因此復雜度與障礙點有關；另一個是針對整個矩形來設計的，因此復雜度與矩形的面積有關。雖然兩個演算法看起來有著巨大的差別，但他們的本質是相通的，都是利用極大化思想，從枚舉所有的極大有效子矩形入手，找出解決問題的方法。
需要注意的是，在解決實際問題是僅靠套用一些現有演算法是不夠的，還需要對問題進行全面、透徹的分析,找出解題的突破口。
此外，如果採用極大化思想，前面提到的兩種演算法的復雜度已經不能再降低了，因為極大有效子矩形的個數就是O(NM)或O(S2)的。如果採用其他演算法，理論上是有可能進一步提高演算法效率，降低復雜度的。
七、 附錄：
1、幾個例題的原題。 見論文附件.doc
2、例題的程序。 見論文附件.doc
說明：所有程序均在Free Pascal IDE for Dos, Version 0.9.2上編譯運行
參考書目
1、 信息學奧林匹克 競賽指導
----1997～1998競賽試題解析
吳文虎 王建德 著
2、 IOI99中國集訓隊優秀論文集
3、 信息學奧林匹克（季刊）
4、 《金牌之路 競賽輔導》
江文哉主編 陝西師范大學出版社出版
J. C語言 編程題中 時間限制 500ms是指編譯時間要小於0.5s么
你在參加編程競賽？
時間是指運行時間不超過0.5秒