orz
by StevenLu1103 @ 2020-04-03 19:25:44
tql
by myee @ 2020-04-04 08:37:42
~~哪有蒟蒻刷蓝题的,您是真大佬~~
by myee @ 2020-04-04 08:38:44
@[myee](/user/105050) 我经常刷灰题，还给灰题发题解，您觉得我是蒟蒻吗？我觉得我是。
by programme_C @ 2020-04-04 09:19:46
@[世外明月](/user/123384)
这是一个有趣但是不那么容易一下就能答上来的问题。应该说，主要和测试数据的强度太低有关。
由于您未给出您的解题思路，只有通过阅读您的代码来揣摩。建议您下次提问时，先描述一遍您的解题思路，这样不仅有助于别人快速了解您的解题方法，从而检查您的思路是否正确，另一方面，也可以通过整理思路，理清头绪，发现错误。
在最初始的实现中，您通过枚举每个点是否属于 $k$ 个矩形中的某一个来确定最小面积，时间复杂度为 $k^n$，虽然通过（$check()$）检查这 $k$ 个矩形是否重叠能够剪掉一些搜索分支，但是剩余的搜索空间仍然很大，显然当 $k=4, n=50$ 时会超时。
接着您增加了一个最优化剪枝（$calc()$），此时 Wrong Answer。这很有意思。由于之前是 TLE 80而且后面又 WA 60，使得您坚信您的算法是正确的。但是实际上您的 $DFS$ 存在一个很大的潜在问题。即按照您的方法，很可能造成这样一种情况：所有点都已经位于您构建的矩形之中，但是矩形的数量却不足 $k$ 个，而这种情况下的面积不是最优的，因为还可以对其中任意的一个矩形进行再次划分，使得结果可能更优，因此应该使得划分的矩形数量达到 $k$ 个。
例如，对于以下随机生成的测试数据：
```
50 4
249 20
147 7
19 388
384 312
324 236
123 10
451 304
456 197
312 287
72 196
65 225
387 169
217 40
478 162
425 226
247 322
75 420
307 394
452 94
330 191
201 276
326 200
143 398
184 27
223 202
427 3
172 34
74 59
469 135
362 298
366 393
312 108
248 442
282 365
55 199
221 112
58 2
401 46
74 201
403 331
334 43
325 75
135 252
388 145
190 103
242 249
103 55
243 300
164 351
296 25
```
第一次更新最优面积 $ans$ 时，当前的递归深度 $stp$、矩形面积之和 $sum$、最优面积 $ans$、四个矩形的左下角和右上角坐标分别为：
```
stp = 51 sum = 3250152 ans = 10000007
rectangle[1] = [19 2 478 442]
rectangle[2] = [1007 1007 -1 -1]
rectangle[3] = [1007 1007 -1 -1]
rectangle[4] = [1007 1007 -1 -1]
```
可以看到，除了第一个矩形以外（该矩形已经将所有点包括进来了，所以您的 $DFS$ 过程停止继续搜索），其他三个矩形都是无效的。后续的几次更新都是存在这个问题，因此得到的解有可能是错误的。
后续的几次更新分别为：
```
stp = 51 sum = 2233629 ans = 3250152
rectangle[1] = [19 3 478 442]
rectangle[2] = [58 2 58 2]
rectangle[3] = [1007 1007 -1 -1]
rectangle[4] = [1007 1007 -1 -1]
stp = 51 sum = 2223990 ans = 2233629
rectangle[1] = [19 2 478 420]
rectangle[2] = [248 442 248 442]
rectangle[3] = [1007 1007 -1 -1]
rectangle[4] = [1007 1007 -1 -1]
stp = 51 sum = 1207467 ans = 2223990
rectangle[1] = [19 3 478 420]
rectangle[2] = [248 442 248 442]
rectangle[3] = [58 2 58 2]
rectangle[4] = [1007 1007 -1 -1]
```
从这后续的几次更新正好可以解释为什么之前是 TLE 80，然后又是 WA 60。我猜测很可能是前几组测试数据的 $k$ 较小（估计 $k<=2$），因此一方面运行时间较短，程序不会超时。另外一方面，由于您的代码中在更新最小值时，至少有一个矩形是符合要求的，有时候还有两个矩形符合要求，那么当 $k<=2$，刚好就满足条件了，因此成为了正确解。
但是为什么在原基础上加了个类似迭代加深的判断就 Accepted 了呢？我猜测纯粹是由于测试数据比较特殊（可能是 $n$ 较小，数据强度很弱），加上您的运气也好的原因，当前计算的矩形面积恰好是最小的。
为了验证，我增加了合法矩形数目的检查：
```
int getCntOfValidRectangle()
{
int cnt = 0;
for (int i = 1; i <= k; i++) if (mx[1][i] != -1) cnt++;
return cnt;
}
if (stp == n + 1)
{
assert(getCntOfValidRectangle() == k);
ans = min(ans, calc());
return;
}
```
发现除了第一个测试点 Accepted 外，其他几个测试点均为 Runtime Error。另外一个您加的递归深度判断并不是迭代加深搜索的应用，应该是由于题目测试数据较弱使得恰好通过。我测试了一下，对于:
```
if(calc()>=ans&&stp>=10)
{
return;
}
```
只要将 $stp$ 设置为大于等于6均能获得 Accepted。
后面您意识到了这个问题，即矩形的个数需要达到 $k$ 才会最优，因此你检查是否所有矩形内均包含点，但是由于您的算法效率不高，因此 TLE。
如果您可以下载测试数据，可以自行验证一下看是不是这样的，如果我的猜测不符，还望您告知，我也想知道究竟是什么原因。
by metaphysis @ 2020-04-04 13:02:42
@[metaphysis](/user/333388) 太感谢了！！！接下去我会去研究一下如何提高程序的速度。（第一次见到这么热心的人）
by tommy0221 @ 2020-04-04 13:42:27
忽然想到一个办法，收到您的启发，已经AC。
在calc里面利用vis加一个特判即可（感觉我好傻啊）
```cpp
#include<bits/stdc++.h>
using namespace std;
#define rint register int
inline int rd(){
int x=0,f=1;
char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)) x=x*10+(ch^48),ch=getchar();
return x*f;
}
const int N=60;
const int inf=1007;
const int Inf=10000007;
int n,k,x[N],y[N],ans=Inf;
int mx[2][5],my[2][5];
bool vis[5];
inline void upd(int i,int j) {
mx[0][j]=min(mx[0][j],x[i]);
mx[1][j]=max(mx[1][j],x[i]);
my[0][j]=min(my[0][j],y[i]);
my[1][j]=max(my[1][j],y[i]);
}
inline bool in(int X1,int Y1,int X2,int Y2,int X,int Y) {
return X1<=X&&X<=X2&&Y1<=Y&&Y<=Y2;
}
inline bool check() {
for(rint i=1;i<=k;++i) {
for(rint j=1;j<=k;++j) {
if(i==j)continue;
if(in(mx[0][i],my[0][i],mx[1][i],my[1][i],mx[0][j],my[0][j]))return 0;
if(in(mx[0][i],my[0][i],mx[1][i],my[1][i],mx[0][j],my[1][j]))return 0;
if(in(mx[0][i],my[0][i],mx[1][i],my[1][i],mx[1][j],my[0][j]))return 0;
if(in(mx[0][i],my[0][i],mx[1][i],my[1][i],mx[1][j],my[1][j]))return 0;
}
}
return 1;
}
inline int calc() {
int sum=0;
for(rint i=1;i<=k;++i)sum+=vis[i]?(mx[1][i]-mx[0][i])*(my[1][i]-my[0][i]):0;
return sum;
}
void dfs(int stp) {
if(!check())return;
if(calc()>=ans)return;
if(stp==n+1) {ans=min(ans,calc());return;}
for(rint i=1;i<=k;++i) {
int tx0=mx[0][i],ty0=my[0][i],tx1=mx[1][i],ty1=my[1][i],v=vis[i];
upd(stp,i);vis[i]=1;dfs(stp+1);
mx[0][i]=tx0,my[0][i]=ty0,mx[1][i]=tx1,my[1][i]=ty1,vis[i]=v;
}
}
inline void init() {
for(rint i=1;i<=k;++i)mx[0][i]=my[0][i]=inf;
for(rint i=1;i<=k;++i)mx[1][i]=my[1][i]=-1;
}
signed main() {
n=rd(),k=rd(),init();
for(rint i=1;i<=n;++i)x[i]=rd(),y[i]=rd();
dfs(1);
printf("%d\n",ans);
return 0;
}
```
by tommy0221 @ 2020-04-04 13:44:29
其实我第二份代码已经意识到了您说的问题，但是表达能力太差导致您没理解。并且在码第2份代码的时候加了个很蠢的最优性剪枝，也能避免这个问题。其实第3份代码那个剪枝很好想的qwq
by tommy0221 @ 2020-04-04 13:46:32
我下载过数据，您猜测的很准，感谢！！！
by tommy0221 @ 2020-04-04 13:47:21
@[世外明月](/user/123384)
有空请您访问我的 [CSDN博客](https://blog.csdn.net/metaphysis)，里面有我写的一本书，内有编程竞赛相关内容的介绍，并附有对应的练习题目（题目源自UVa OJ），可免费下载此书的PDF版本：[《C++，挑战编程——程序设计竞赛进阶训练指南》](https://blog.csdn.net/metaphysis/article/details/90288252)。可以的话，还烦您向对编程感兴趣的朋友推荐一下我的博客和书，感谢！
by metaphysis @ 2020-04-04 14:57:29