今天复习了状压（预习）
特殊方格棋盘
题目描述
在n*n(n≤20)的方格棋盘上放置 n 个车，某些格子不能放，求使它们不能互相攻击的方案总数。
#include <bits/stdc++.h> using namespace std; const int maxn=(1<<20)-1; typedef long long ll; int n,m,x,y,s,a[25]; ll f[maxn]; int lowbit(int x) {return x&-x;} int main() { scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { scanf("%d%d",&x,&y);//（x,y）处不可放车 a[x]+=1<<(y-1);//a[x]数组标记第i行状态，第j列不可放车 } f[0]=1;//初始化转移条件 int Maxn=(1<<n)-1;//每行有2的n次方可能，转为二进制2的n次方-1记录 for(int S=1;S<=Maxn;S++) { int cnt=0; for(int i=S;i;i-=lowbit(i)) cnt++;//S状态下已放入多少车（又为前cnt行，题目要求可得每行只能放一个且每行都必须放即每行有且只能放一个） for(int i=S;i;i-=lowbit(i)) { if(!(a[cnt]&lowbit(i))) {//与前cnt行状态不矛盾 s=S^lowbit(i);//上一行状态 f[S]+=f[s];//上一行状态转移 } } } printf("%lld",f[Maxn]);//末尾状态所得方案数 return 0; }
互不侵犯
题目描述
在N×N的棋盘里面放K个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共8个格子。
#include <bits/stdc++.h> using namespace std; const int maxn=1<<10; int n,k,cnt[maxn]; typedef long long ll; ll ans,dp[20][maxn][100]; bool vis[maxn]; int main() { scanf("%d%d",&n,&k); int Maxn=(1<<n)-1; for(int i=0;i<=Maxn;i++) { int temp=i; while(temp) { if(temp%2==1) cnt[i]++; temp/=2; } } for(int i=0;i<=Maxn;i++) { if(((i<<1)&i)==0) vis[i]=1; } for(int i=0;i<=Maxn;i++) { if(vis[i]&&cnt[i]<=k) dp[1][i][cnt[i]]=1; } for(int i=2;i<=n;i++) { for(int j=0;j<=Maxn;j++) { if(vis[j]) { for(int s=0;s<=Maxn;s++) { if(!vis[s]) continue; if((s&j)!=0||((s<<1)&j)!=0||((s>>1)&j)!=0) continue; for(int l=k;l>=cnt[j];l--) { dp[i][j][l]+=dp[i-1][s][l-cnt[j]]; } } } } } for(int i=0;i<=Maxn;i++) ans+=dp[n][i][k]; printf("%lld ",ans); return 0; }
旅游景点 Tourist Attractions
题目描述
输入格式
第一行包含 3 个整数 N(2<=N<=20000),M(1<=M<=200000),K(0<=K<=20),意义如上所述。以下 M 行,每行包含 3 个整数 X,Y,Z,(1<=X<y<=n, 1<="Z=1000)表示城市 X与 Y 之间有一条双向道路。你可以认为输入文件使得一定能自成都到上海以及任何 FGD 想要去的城市。"下一行包含一个整数 G(0<=G<=K*(K-1)/2)。以下 G 行,每行包含 2 个整数 X Y,(2<=X,Y<=K+1)表示 FGD 想要在游览城市Y 之前,一定要游览城市 X。你可以认为至少存在一种满足所有限制的游览方案。
样例省略啦
这个要和最短路知识结合了♦
#include <bits/stdc++.h> using namespace std; const int maxn=1<<20,maxv=2e4+10,Inf=0x3f3f3f3f; #define pa pair<int,int> typedef long long ll; int n,m,k,t,x,y,cnt,ans,d[maxv],head[maxv],a[25],dis[25][25],f[maxn][25]; bool vis[maxv]; struct Edge{ int to,next,dis; }e[maxn]; void add(int u,int v,int z) { e[++cnt].next=head[u]; head[u]=cnt; e[cnt].to=v; e[cnt].dis=z; } void Dijkstra(int x) { priority_queue<pa,vector<pa>,greater<pa> >q;//队列优化算法 for(int i=1;i<=n;i++) { d[i]=Inf; vis[i]=0; } d[x]=0; q.push(make_pair(0,x)); while(!q.empty()) { int now=q.top().second; q.pop(); if(vis[now]) continue; vis[now]=1; for(int i=head[now];i;i=e[i].next) { if(d[now]+e[i].dis<d[e[i].to]) { d[e[i].to]=d[now]+e[i].dis; q.push(make_pair(d[e[i].to],e[i].to)); } } } for(int i=1;i<=k+1;i++) dis[x][i]=d[i]; dis[x][0]=d[n];//记录i到n的最短路 } int main() { scanf("%d%d%d",&n,&m,&k); int Maxn=(1<<k)-1;//k为限制，分别记录k个点每个点是否到达 int u,v,z; for(int i=1;i<=m;i++) { scanf("%d%d%d",&u,&v,&z); add(u,v,z); add(v,u,z);//建图，无向 } for(int i=1;i<=k+1;i++) Dijkstra(i);//计算第i个点到各个点最短距离 scanf("%d",&t); for(int i=1;i<=t;i++) { scanf("%d%d",&x,&y); a[y]+=1<<(x-2);//位置左移，优化空间
//到达第y个点前，必须先游览过第x个点;
但是与最短路径经过y点不矛盾，可以路过不游览y点
} memset(f,-1,sizeof(f));//距离可能为0，故将其初始化-1 f[0][1]=0;//起始转移条件 for(int s=0;s<=Maxn;s++) {//枚举游览状态 for(int i=1;i<=k+1;i++) {//前状态游览城市位置 if(f[s][i]!=-1) { for(int j=2;j<=k+1;j++) {//后状态游览城市位置 if((s&a[j])==a[j]) {//检查s状态下经过第i个点前状态是否满足限制 int to=(s|(1<<(j-2)));//或运算取后位置状态 if(f[to][j]>f[s][i]+dis[i][j]||f[to][j]==-1) f[to][j]=f[s][i]+dis[i][j];//s状态（前状态）第i个城市（前位置）转移为to状态（后状态）第j个城市（后位置）取最优;或to状态j位置还未被赋值将其赋值 } } } } } ans=Inf; for(int i=1;i<=k+1;i++) { if(f[Maxn][i]!=-1) ans=min(ans,f[Maxn][i]+dis[i][0]);//因为可以经过城市而不游览，所以状态满足Maxn时（即2～k+1个城市均已游览过） 末位置不一定是k+1但一定是2~k+1中的一个数;
枚举Maxn状态下不同末位置求其最小值 } printf("%d",ans); return 0; }//lsyl
