P1283 题解

Lysra · 2023-11-08 22:08:25 · 题解

一维状压 DP 做法

看到题解区要么用深搜，要么用二维 DP，于是来分享一下本题一维 DP 怎么做。

设 dp_i 表示所有矩形的状态用二进制表示为 i 时拿起刷子的最少次数。

如果 DP 只有一维，那么转移就会相对困难一些，最直接的想法枚举每一个颜色哪些位置是能够涂的（根据贪心不难想到，位置数量越多越好），然后用现在的状态去更新未来的状态。

然而问题又出现了，如果一个矩阵的上方还有一个相同颜色的矩阵，且上方的矩阵在本轮中可以被涂，假设下方的矩阵在上方的矩阵更新后也可以被涂，那么实际上我们是更新不到下方的矩阵的。

为了解决这个问题，我们观察到 x，y 数据范围皆在 100 以内，所以可以用一种很暴力的方法：每轮进行 100 次更新，这样就可以保证所有能够被涂的矩阵都不会漏掉。

代码：

#include<bits/stdc++.h>
#define int long long
#define N 20
#define M 25
#define INF 1e18
using namespace std;
struct node{
    int x,y,xx,yy,col;
}e[N];
int n,m,dp[1<<N],ned[M][M],c[M][M],qwq;
bool vis[N];
signed main(){
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>e[i].y>>e[i].x>>e[i].yy>>e[i].xx>>e[i].col;
        c[e[i].col][++c[e[i].col][0]]=i;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i!=j&&e[j].yy==e[i].y&&e[j].xx>e[i].x&&e[j].x<e[i].xx){
                ned[i][++ned[i][0]]=j;
            }
        }
    }
    for(int i=0;i<(1<<n);i++) dp[i]=INF;
    dp[0]=0;
    for(int i=0;i<(1<<n);i++){
        for(int j=1,tot;j<=20;j++){
            qwq=0,tot=100;
            for(int i=1;i<=n;i++) vis[i]=false;
            for(;tot--;)
            for(int k=1;k<=c[j][0];k++){
                int y=c[j][k],fl=1;
                for(int q=1;q<=ned[y][0];q++){
                    if((1ll<<(ned[y][q]-1))&i||vis[ned[y][q]]) continue;
                    fl=0;break;
                }
                if(fl) vis[y]=true;
            }
            for(int i=1;i<=n;i++){
                if(vis[i]) qwq+=(1ll<<(i-1));
            }
            dp[i|qwq]=min(dp[i|qwq],dp[i]+1);
        }
    }
    cout<<dp[(1<<n)-1];
    return 0;
}