1 solutions

  • 0
    @ 2023-10-25 21:20:46

    难度:

    算法: 状压 dp,搜索

    看到数据范围就想到应该是指数级时间复杂度的算法。最常见的指数级算法是搜索,但是...是不是还有...

    状压 dp?洛谷上的标签都告诉我们是状压 dp。

    把当前的状态压缩成一个 nn 位二进制数,每一位对应一块板子是否已被涂色,是记为 11,否记为 00。然后进行状压 dp。过程如下:

    f[k][i]f[k][i] 表示当前状态为 kk,上一个涂了 ii

    初始状态:记 f[0][i]=0f[0][i]=0,其余为无穷大。

    转移:

    ii 的颜色与 jj 的颜色相同且 k(1<<(i1))k\oplus (1<<(i-1)) 不为 00,则 dp[k][i]=min(dp[k][i],f[k(1<<(i1))][j])dp[k][i]=min(dp[k][i],f[k\oplus (1<<(i-1))][j])

    否则,dp[k][i]=min(dp[k][i],f[k(1<<(i1))][j]+1)dp[k][i]=min(dp[k][i],f[k\oplus (1<<(i-1))][j]+1)

    记得判断可行性。

    最后统计 min(dp[2n1][i])min(dp[2^n-1][i]) 即可。

    注:上文中 i,ji,j 均为 [1,n][1,n] 中的整数,\oplus 为异或。

    代码:

    #include<bits/stdc++.h>
    using namespace std;
    int n,xa,ya,xb,yb,c[20],d[110][110],s[20][20],f[65600][20],t,ans;
    vector<int> e[20];
    int main(){
    	memset(f,0x3f3f3f,sizeof(f));
    	memset(f[0],0,sizeof(f[0]));
    	ans=f[1][1];
    	scanf("%d",&n);
    	for(int i=1;i<=n;i++){
    		scanf("%d%d%d%d%d",&xa,&ya,&xb,&yb,&c[i]);
    		for(int j=xa+1;j<=xb;j++){
    			for(int k=ya+1;k<=yb;k++){
    				d[j][k]=i;
    			}
    		}
    	}
    	for(int i=1;i<=100;i++){
    		for(int j=1;j<=100;j++){
    			if(d[i][j]!=0&&d[i-1][j]!=0&&d[i-1][j]!=d[i][j]) s[d[i][j]][d[i-1][j]]=1;
    		}
    	}
    	for(int i=1;i<=n;i++){
    		for(int j=1;j<=n;j++){
    			if(s[i][j]==1){
    				e[i].push_back(j);
    			}
    		}
    	}
    	for(int k=1;k<(1<<n);k++){
    		for(int i=1;i<=n;i++){
    			if(!(k&(1<<(i-1)))) continue;
    			t=0;
    			for(int j=0;j<int(e[i].size());j++){
    				if(!(k&(1<<(e[i][j]-1)))){
    					t=1;
    					break;
    				}
    			}
    			if(t) continue;
    			for(int j=1;j<=n;j++){
    				if(c[i]==c[j]&&k^(1<<(i-1))) f[k][i]=min(f[k][i],f[k^(1<<(i-1))][j]);
    				else f[k][i]=min(f[k][i],f[k^(1<<(i-1))][j]+1);
    			}
    		}
    	}
    	for(int i=1;i<=n;i++) ans=min(ans,f[(1<<n)-1][i]);
    	printf("%d",ans);
    	return 0;
    }
    
    • 1

    Information

    ID
    25
    Time
    1000ms
    Memory
    512MiB
    Difficulty
    7
    Tags
    # Submissions
    21
    Accepted
    7
    Uploaded By