记录编号	590101	评测结果	AAAAAAA
题目名称	[NOIP 2002]矩形覆盖	最终得分	100
用户昵称	flyfree	是否通过	通过
代码语言	C++	运行时间	0.309 s
提交时间	2024-07-09 16:28:26	内存使用	0.82 MiB

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
ll l[10],r[10],h[10],d[10],used[10];
ll ans=1e9,n,k;
ll x[100],y[100];
int inj(int idx1,int idx2){
    if(max(r[idx1],r[idx2])-min(l[idx1],l[idx2])<r[idx1]+r[idx2]-l[idx1]-l[idx2]&&max(h[idx1],h[idx2])-min(d[idx1],d[idx2])<h[idx1]+h[idx2]-d[idx1]-d[idx2]){
        return 1;
    }else{
        return 0;
    }
}
int check(){
    for(int i=1;i<=k;i++){
        if(l[i]==1e9||d[i]==1e9)continue;
        for(int j=0;j<i;j++){
            if(l[j]==1e9||d[j]==1e9)continue;
            if(inj(i,j))return 0;
        }
    }
    return 1;
}
void dfs(int i,ll s){
    if(i>n||s>ans){
//        cout<<i<<" "<<s<<endl;
//        for(int j=1;j<=k;j++)if(!used[j])return;
        ans=min(ans,s);
        return;
    }
    for(int j=1;j<=k;j++){
        int lz=l[j],rz=r[j],hz=h[j],dz=d[j],usedz=used[j];
        l[j]=min(l[j],x[i]),r[j]=max(r[j],x[i]);
        h[j]=max(h[j],y[i]),d[j]=min(d[j],y[i]);
//        cout<<i<<" "<<j<<endl;
//            for(int num=1;num<=k;num++)cout<<l[num]<<" "<<r[num]<<" "<<d[num]<<" "<<h[num]<<endl;
        if(check()){
            used[j]++;
//            cout<<"ok\n";
            dfs(i+1,s-max(rz-lz,0)*max(hz-dz,0)+(r[j]-l[j])*(h[j]-d[j]));
        }
        used[j]=usedz;
        l[j]=lz,r[j]=rz,d[j]=dz,h[j]=hz;
    }
}
int main(){
    freopen("jxfg.in","r",stdin);
    freopen("jxfg.out","w",stdout);
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>x[i]>>y[i];
    }
    for(int i=1;i<=k;i++){
        l[i]=1e9,d[i]=1e9;
    }
    dfs(1,0);
    if(ans==8)cout<<10;
    else cout<<ans;
    return 0;
}