自动搬运

查看原文

来自洛谷，原作者为

	SentoAyaka 人生若只如初见，何事秋风悲画扇

搬运于2025-08-24 22:52:14，当前版本为作者最后更新于2023-12-01 16:13:32，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

离散化后考虑设 $f_{i,j,0\sim 4}$ 表示到 $i$，用了 $j$ 个矩形，当前上下没有矩形$(0)$，上面没矩形$(1)$，下面没矩形$(2)$，上下都有矩形但不联通$(3)$，上下都有矩形且联通$(4)$，转移即可。

const int N=1e3+5,M=1.5e7+5,inf=0x3f3f3f3f;
int n,m,K,dp[2][N][5];bitset<M> mp[2];
inline void chkmin(int &x,int y){if(x>y)x=y;}
//0:no_all
//1:no_up
//2:no_down
//3:all_but_no_connect
//4:all_and_connect
void MAIN(){
    m=read(),K=read(),n=read();vec w;
    for(int i=1;i<=m;i++){
        int x=read(),y=read();
        mp[x-1][y]=1;w.pb(y);
    }
    sort(w.begin(),w.end()),w.erase(unique(w.begin(),w.end()),w.end());
    memset(dp,0x3f,sizeof dp);
    int tot=w.size();dp[0][0][0]=0;
    for(int i=0;i<tot;i++){
        int x=w[i],val=((i==0||i==tot)?1:w[i]-w[i-1]);auto &f=dp[i&1],&g=dp[i&1^1];
        memset(g,0x3f,sizeof g);
        for(int j=0;j<=K;j++){
            if(!mp[0][x]&&!mp[1][x])chkmin(g[j][0],f[j][0]);
            if(!mp[0][x])chkmin(g[j][1],f[j][1]+1*val);
            if(!mp[1][x])chkmin(g[j][2],f[j][2]+1*val);
            chkmin(g[j][3],f[j][3]+2*val);
            chkmin(g[j][4],f[j][4]+2*val);
            int res=inf;for(int k=0;k<=4;k++)chkmin(res,f[j][k]);
            chkmin(g[j+1][4],res+2);
            chkmin(g[j+2][3],res+2),
            chkmin(g[j+1][3],min(f[j][1],f[j][2])+1+val);
            if(!mp[0][x]){
                int op=1;
                chkmin(g[j+1][op],res+1),chkmin(g[j][op],f[j][3]+val);
            }
            if(!mp[1][x]){
                int op=2;
                chkmin(g[j+1][op],res+1),chkmin(g[j][op],f[j][3]+val);
            }
        }
    }
    int ans=inf;
    for(int j=0;j<=K;j++)for(int k=0;k<=4;k++)chkmin(ans,dp[tot&1][j][k]);
    cout<<ans<<"\n";
}