题解：P1283 平板涂色

· · 题解

状压 DP，思路：

不知道怎么直接预处理各种各样的条件，只能一点一点在循环里写了。 这些可能对找 bug 和没考虑到的情况有用。

给出几个区块，我们在涂色时需要把与它本身上方有重叠的区块涂色，首行没有前置区块，我们要求最少换笔数，注意不是落笔数，只要是相同颜色的画笔，可以在任意符合规则的位置，即无需区块相邻，都可以用一笔完成。

题目要求需要前置区块完成才可进行这一块，所以想到拓扑，我们用链式前向星来存前置区块。同时我用结构体来存区块。

再看颜色要求 c\leq20,n\leq16 应数据范围，我们可以用状态压缩来记录已经画了哪几个区块。

对于 dp 我们记 f_{i,j} 当区块状态为 i 时最后一笔的颜色为 j。

状态转移：我们找一个存在于状态 i 中的点为 j，且颜色为 col，前一个状态的落笔颜色为 k 如果 j 的颜色与 k 相等，则 f_{i,col}=\min(f_{i-2^{j-1},k})，否则就将换笔数加 1。

这就是整体思路。接下来还有我自己的一些判断条件，我会在代码里用注释体现。

这些花了一个下午。

接下来是代码。

#include<bits/stdc++.h>
using namespace std;
int in(){
    int ans=0,f=1;
    char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
    for(;isdigit(c);c=getchar()) ans=ans*10+c-'0';
    return ans*f;
}//快读 
struct F{
    int xl,xr,yu,yd,col;
}sq[50];//区块 
int n,m;
int fir[1010],ne[1010],en[1010],cnt;//链式前向星 
void add(int u,int v){
    cnt++;
    ne[cnt]=fir[u];
    en[cnt]=v;
    fir[u]=cnt;
}
int f[100010][50],d[1010];
bool check(int s,int p){//判断当状态s时，区块p是否可以画 
    for(int i=fir[p];i;i=ne[i]){
        int u=en[i];
        if(((1<<(u-1))&s)==0) return 0;
    }
    return 1;
} 
bool cd(int i,int j){//判断区块i，j是否有重叠 
    int xl1=sq[i].xl,xr1=sq[i].xr;
    int xl2=sq[j].xl,xr2=sq[j].xr;
    if(xr1<=xl2) return 0;
    if(xr2<=xl1) return 0;
    return 1;
}
bool ch_col(int s,int p,int col){
    //判断当状态s时  当前区块为p  s的上一个状态（去除p）的落笔颜色中是否包含col
        //如果没有就不能遍历 
    if(d[p]==0&&s==(1<<(p-1))) return 1;//如果是无前置区块，则可以直接落笔 
    s-=(1<<(p-1));
    for(int i=1;i<=n;i++){
        if(s&(1<<(i-1))){
            if(col==sq[i].col) return 1;
        }
    }
    return 0;
}
int main(){
//  freopen("data.in","r",stdin);
    n=in();
    for(int i=1;i<=n;i++){
        sq[i].yu=in();
        sq[i].xl=in();
        sq[i].yd=in();
        sq[i].xr=in();
        sq[i].col=in();
        m=max(m,sq[i].col);//最大颜色 
    }
    //找自己的前置区块 
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(sq[i].yd==sq[j].yu && i!=j){
                if(cd(i,j)){//i是j的前置区块
                    add(j,i);
                    d[j]++;//记录有多少个前置区块
                }
            }
        }
    }
    //状压dp 
    memset(f,0x3f,sizeof(f));
    for(int i=1;i<=m;i++) f[0][i]=1;
    for(int i=1;i<(1<<n);i++){
        for(int j=1;j<=n;j++){
            int to=i-(1<<(j-1));//前一个状态to 
            if(check(to,j) && ((i&(1<<(j-1)))!=0)){//j在i状态中且j的前置区块完成 
                for(int k=1;k<=m;k++){
                    if(sq[j].col==k && (ch_col(i,j,k))){//颜色相同 且颜色存在于状态i中 
                        f[i][sq[j].col]=min(f[i][sq[j].col],f[to][k]);
                    }
                    else f[i][sq[j].col]=min(f[i][sq[j].col],f[to][k]+1);
                }
            }
        }
    }
    int ans=0x7fffffff;
    for(int i=1;i<=m;i++){
        ans=min(ans,f[(1<<n)-1][i]);
    }//将所有可能落笔颜色遍历 
    cout<<ans;
    return 0;
}