题解 P1283 【平板涂色】

· · 题解

一看到n<=16,颜色<=20，马上就要想到裸的状压dp，

设dp[S][i]表示在集合S(已经涂的矩形的集合)中，最后涂色的颜色是i，所需的最少拿刷子的次数。至于集合，就是用二进制表示。

先预处理出每个矩形上面有哪些矩形，这个由于数据范围比较小，都不用离散化，直接开个二维数组弄个矩形覆盖就行了。

至于具体的Dp，应该还算是比较好写的。

枚举一下最后一次涂的是第j个矩形，而第j个矩形的颜色是col[j]，当然，这个第j个矩形必须满足两个限制：

1.j属于S

2.j上面的矩形都属于S

那么Dp(S,col[j])=min(Dp(S-(1<<(j-1)),k)+1){枚举另一个颜色k，并且k!=col[j]}

Dp(S,col[j])=min(Dp(S-(1<<(j-1)),col[j]))

这个还是很好理解的。

参考代码：

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
template<class T>void ChkMin(T &a,T b){if (a>b)a=b;}
const int INF=0x3f3f3f3f;
const int N=101;
const int M=21;
int lx[M],size[M],ly[M],col[M],rx[M],ry[M];
int n,a[N][N],dp[1<<16+1][M],up[M][M];
inline bool in(int i,int S){
    return (S>>(i-1))&1;
}
inline bool ok(int i,int S){
    bool flag=true;
    for (int j=1;j<=size[i] && flag;j++)flag&=in(up[i][j],S);
    return flag;
}
int main(){
    scanf("%d",&n);
    for (int i=1;i<=n;i++){
        scanf("%d%d%d%d%d",&lx[i],&ly[i],&rx[i],&ry[i],&col[i]);
        for (int x=lx[i];x<rx[i];x++)
            for (int y=ly[i];y<ry[i];y++)
                a[x][y]=i;
    }
    for (int i=1;i<=n;i++){
        if (!lx[i])continue;
        lx[i]--;
        for (int j=ly[i]+1;j<=ry[i];j++)
            if (a[lx[i]][j]!=a[lx[i]][j-1])up[i][++size[i]]=a[lx[i]][j-1];
        if (a[lx[i]][ry[i]]==a[lx[i]][ry[i]-1])up[i][++size[i]]=a[lx[i]][ry[i]-1];
    }
    memset(dp,0x3f,sizeof(dp));
    for (int i=1;i<=20;i++)
        dp[0][i]=1;
    for (int i=1;i<(1<<n);i++){
        for (int j=1;j<=n;j++)
            if (in(j,i) && ok(j,i)){
                for (int k=1;k<=20;k++)
                    if (k!=col[j])ChkMin(dp[i][col[j]],dp[i-(1<<(j-1))][k]+1);
                ChkMin(dp[i][col[j]],dp[i-(1<<(j-1))][col[j]]);
            }
    }
    int ans=INF;
    for (int i=1;i<=20;i++)
        ChkMin(ans,dp[(1<<n)-1][i]);
    printf("%d",ans);
    return 0;
}