Description
在一個N*N的區域玩積木遊戲，每個單元格正好跟積木的底面相等，每個單元格裡放有若幹個積木，Alice想重新擺放積木，使得每個單元格最多隻能放一個積木，并且所有積木正好形成一個矩形。
把一個積木從一個位置移到另一個位置稱為一次操作。
給出初始狀态，程式設計計算最少需要多少次操作才能達到上述要求。
Input
第一行包含兩個整數N和M(1<=N<=100，1<=M<=N^2)，表示區域大小以及積木的數量。
接下來M行，每行包含兩個整數R和C(1<=R,C<=N)，表示每個積木放置的位置。
Output
輸出最少操作次數。輸入保證有解。
分析
可以把這題變成用一個面積m的矩形，最多可以覆寫多少個有積木的區域。（why?自行腦補，可畫圖）。
然後就簡單了，先預處理出從1,1到i,j這個矩形中有多少個區域有積木，記在s[i,j]。
枚舉面積為m的矩形的邊長，用
f[i,j]=s[i,j]−s[i−m1,j]−s[i,j−n1]+s[i−m1,j−n1]
計算，其中f[i,j]表示用i,j為右下角的矩形中的有積木的區域個數。
m1,n1為矩形面積。
答案為總個數—可以覆寫最多個有積木的區域。
代碼
var
i,j,k:longint;
f:array[..,..] of longint;
a:array[..,..] of longint;
b:array[..] of longint;
n1,m1:longint;
n,m:longint;
ans,max:longint;
begin
readln(n,m);
for i:= to m do
begin
readln(j,k);
f[j,k]:=;
end;
for i:= to n do
for j:= to n do
f[i,j]:=f[i-,j]+f[i,j-]-f[i-,j-]+f[i,j];
b[]:=;
for i:= to m do
begin
if m mod i=
then
begin
b[]:=b[]+;
b[b[]]:=i;
end;
end;
for i:= to b[] do
begin
n1:=b[i];
m1:=m div b[i];
if (n1>n) or (m1>n)
then continue;
max:=;
for j:=n1 to n do
for k:=m1 to n do
begin
if f[j,k]-f[j-n1,k]-f[j,k-m1]+f[j-n1,k-m1]>max
then max:=f[j,k]-f[j-n1,k]-f[j,k-m1]+f[j-n1,k-m1];
end;
if ans<max then ans:=max;
end;
write(m-ans);
end.
轉載于:https://www.cnblogs.com/a-loud-name/p/6184757.html