1 solutions
-
0
难度: 蓝
算法: 状压 dp,搜索
看到数据范围就想到应该是指数级时间复杂度的算法。最常见的指数级算法是搜索,但是...是不是还有...
状压 dp?
洛谷上的标签都告诉我们是状压 dp。把当前的状态压缩成一个 位二进制数,每一位对应一块板子是否已被涂色,是记为 ,否记为 。然后进行状压 dp。过程如下:
记 表示当前状态为 ,上一个涂了 。
初始状态:记 ,其余为无穷大。
转移:
如 的颜色与 的颜色相同且 不为 ,则 。
否则,。
记得判断可行性。
最后统计 即可。
注:上文中 均为 中的整数,为异或。
代码:
#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