网站设计书怎么写/怎么建网站教程图解

https://www.luogu.org/problemnew/show/P1034

这道题的数据是真的水，唯一的难点就是确定好爆搜的状态，我们爆搜每个矩形包含那几个点，存在数组里，再加一个最优化剪枝和可行性剪枝，判断答案是否更优或者矩形是否相交即可。

code:

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;const int N=60, K=5, INF=0x3f3f3f3f;
struct point {int x, y;
} p[N];
int n, k, ans=INF, cnt[K], a[K][N];bool check(int pos) {int i, j, S=0, top[K], bottom[K], left[K], right[K];memset(top, -1, sizeof(top));memset(bottom, INF, sizeof(bottom));memset(left, INF, sizeof(left));memset(right, -1, sizeof(right));for (i=1; i<=k; i++) {for (j=1; j<=cnt[i]; j++) {top[i]=max(p[a[i][j]].y, top[i]);bottom[i]=min(p[a[i][j]].y, bottom[i]);right[i]=max(p[a[i][j]].x, right[i]);left[i]=min(p[a[i][j]].x, left[i]);}//cout << top[i] << " " << bottom[i] << " " << right[i] << " " << left[i] << endl;  }for (i=1; i<=k; i++) {for (j=1; j<=k; j++) {if (cnt[i]==0 || cnt[j]==0) continue;if (i==j) continue;if (right[i]<left[j] || left[i]>right[j] || bottom[i]>top[j] || top[i]<bottom[j]) continue;return false;}}for (i=1; i<=k; i++) {if (cnt[i]==0) continue;S+=(top[i]-bottom[i])*(right[i]-left[i]);if (S>=ans) return false;}if (pos==n+1) ans=S;return true;
}void dfs(int pos) {if (!check(pos)) return ;int i;for (i=1; i<=k; i++) {a[i][++cnt[i]]=pos;dfs(pos+1);a[i][cnt[i]--]=0;}return ;
}int main() {int i;cin >> n >> k;for (i=1; i<=n; i++)cin >> p[i].x >> p[i].y;dfs(1);cout << ans;return 0;
}

https://www.luogu.org/problemnew/show/P1072

非常水的蓝题，是不是标签错了啊。

洛谷博客：https://www.luogu.org/blog/user16215/solution-p1072