状压dp，关键在于用01串将过程中的状态进行压缩且便于存储。这边会涉及到位运算。
由于位运算的优先级比(==)还低，所以记得频繁打上括号以免不幸。
NC20240 互不侵犯King
将每一行的摆放情况用01串来表示，这样就可以将状态压缩。用(f[i][j][k])表示第(i)行摆放情况为(k)且总共已经摆放了(j)个棋子。那么(f[i][j][k]+=f[i-1][j-num[k]][s])，其中(num[k])表示情况为(k)时需要的棋子数量。同时(k)与(s)必须满足：
(((k>>1)&k )==0)
((k&s)==0, ((k>>1)&s)==0, ((k<<1)&s)==0)
另外，各个情况需要的棋子数量可以进行预处理。
#include<bits/stdc++.h> #define fast ios::sync_with_stdio(0),cin.tie(0),cout.tie(0) #define ll long long #define pb push_back using namespace std; const int maxn = 20; int f[maxn][100][(1<<10)+10]; ll num[(1<<10)+10]; void init() { for(int i=0;i<(1<<10);i++) { int m=i; while(m) { if(m%2) num[i]++; m/=2; } } } int main() { int n,k; init(); cin>>n>>k; for(int i=0;i<(1<<n);i++) { if((i&(i<<1))!=0) continue; f[1][num[i]][i]=1; } for(int i=2;i<=n;i++) { for(int j=0;j<=k;j++) { for(int s=0;s<(1<<n);s++) { if((s&(s<<1))!=0) continue; if(num[s]>j) continue; // cout<<i<<' '<<j<<' '<<s<<' '; for(int t=0;t<(1<<n);t++) { if((s&t)==0 && ((s<<1)&t)==0 && ((s>>1)&t)==0) { f[i][j][s]+=f[i-1][j-num[s]][t]; //cout<<i<<' '<<j<<' '<<s<<' '<<' '<<j-num[s]<<' '<<t<<' '<<f[i][j][s]<<' '; } } } } } ll ans=0; for(int i=0;i<(1<<n);i++) { //cout<<i<<' '<<f[n][k][i]<<' '; ans+=f[n][k][i]; } cout<<ans<<' '; }
NC16886 炮兵阵地
上一道题目的加强版，要求左右十字范围内两个都不能有友军，且所有的炮兵都需要站在平原上。
那么首先我们对整张图进行状态压缩处理，用(0)表示平原，用(1)表示山地。再对每一排的士兵摆放状态进行状态压缩，(0)无(1)有。这样的设定会使得当这两者与运算结果为(1)时是非法的。
用(f[s][i][j])表示第(s)行状态为(i)，前一行状态为(j)时士兵的最大数量。此时枚举前两行的状态(k)，当三者都合法时，状态转移方程为(f[s][i][j]=max(f[s][i][j],f[s-1][j][k]+num[i]))，其中(num[i])表示(i)状态下有多少个士兵。
另外，如果枚举所有状态会导致复杂度爆炸，因此，我们先预处理对于每一行而言合法的状态（即十字两格不能有友军），这样在数据范围拉满的情况下也就只有(60)种情况，这样就足够存下了。
#include <bits/stdc++.h> #define ll long long #define pb push_back #define fast ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; const int maxn = 110; string mp[maxn]; int c[maxn]; ll f[maxn][70][70]={0}; vector<int> v; int num[70]={0}; void init(int n) { for (int i = 0; i < (1 << n); i++) { if (!((i << 1) & i) && !((i << 2) & i)) v.pb(i); } } int main() { int n, m; cin >> n >> m; init(m); for (int i = 0; i < n; i++) { cin >> mp[i]; } for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { if(mp[i][j]=='P') c[i+1]=(c[i+1]<<1)+0; else c[i+1]=(c[i+1]<<1)+1; } } int len = v.size(); for (int i = 0; i < len; i++) { int tmp = v[i]; while (tmp) { num[i] += tmp % 2; tmp /= 2; } } for (int s = 1; s <= n; s++) { for (int i = 0; i < len; i++) { for(int j=0;j<len;j++) { for(int k=0;k<len;k++) { if((v[i]&v[j]) || (v[i]&v[k]) || (v[j]&v[k]) || (v[i]&c[s]) || (v[j]&c[s-1]) || (v[k]&c[max(0,s-2)])) continue; f[s][i][j]=max(f[s][i][j],f[s-1][j][k]+num[i]); } } } } ll ans = 0; for (int i = 0; i < len; i++) { for (int j = 0; j < len; j++) { ans = max(ans, f[n][i][j]); } } cout << ans << ' '; }
NC16122 郊区春游
NC16544 简单环
这两道题写在一起是因为这两道题同属于TSP问题。
TSP问题，又称旅行推销员问题，假设一个商人要拜访(n)个城市，每个城市只能拜访一次，并且最后回到原点，问所有路径中的最小权值。
这类问题通常而言，用(f[i][j])表示(i)状态下并且当前处于(j)位置时的最小权值，(i)为(01)串，1表示已经拜访，0表示未拜访。
另外，状态转移方程不仅仅局限于依靠过去推现在，也可以通过现在推将来。
例如NC16122，状态转移方程可以写为：(f[i|nex][k]=min(f[i|nex][k],f[i][j]+G[vi[j]][vi[k]]))，其中(nex=1<<(k-1))。
另外对于这道题，先要进行连通性与最短路径的预处理，(floyd)即可。
#include<bits/stdc++.h> #define ll long long #define pb push_back #define fast ios::sync_with_stdio(0),cin.tie(0),cout.tie(0) using namespace std; const int maxn = 210; const int INF = 0x3f3f3f3f; int n,m,r; int G[maxn][maxn]; int f[1<<16][maxn]; int size=10; int vi[20]; void floyd() { for(int k=1;k<=n;k++) { for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { G[i][j]=min(G[i][j],G[i][k]+G[k][j]); } } } } int main() { fast; cin>>n>>m>>r; int u,v,w; for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { G[i][j]=INF; } } for(int i=1;i<=r;i++) { cin>>vi[i]; } for(int i=0;i<(1<<r);i++) { for(int j=1;j<=n;j++) { f[i][j]=INF; } } for(int i=1;i<=m;i++) { cin>>u>>v>>w; G[u][v]=w; G[v][u]=w; } floyd(); for(int i=1;i<=r;i++) { f[1<<(i-1)][i]=0; } for(int i=1;i<(1<<r)-1;i++) { for(int j=1;j<=r;j++) { int sta=1<<(j-1); if(!(i&sta)) continue; for(int k=1;k<=r;k++) { int nex=1<<(k-1); if(nex&i) continue; f[i|nex][k]=min(f[i|nex][k],f[i][j]+G[vi[j]][vi[k]]); } } } int ans=INF; for(int i=1;i<r;i++) { ans=min(ans,f[(1<<r)-1][i]); } cout<<ans<<' '; }
那么对于另一道题，首先要求这个环要求终点要大于起点（不然统计会乱），状态转移方程与上一题类似，区别仅仅在于统计的是方案数量。转移之后，判断当前点与起点是否有边且环长度是否大于3。最后得到的结果需要除2（因为对于一个环可以顺时针也可以逆时针），那么这里就需要逆元。
#include<bits/stdc++.h> #define pb push_back #define ppb pop_back #define ll long long #define fast ios::sync_with_stdio(0),cin.tie(0),cout.tie(0) using namespace std; const int maxn = 22; const ll mod = 998244353; bool G[maxn][maxn]; ll f[1<<20][maxn]; ll ans[maxn]; int n,m,k; ll Pow(ll a,ll b) { if(b==0) return 1; if(b%2) return a*Pow(a,b-1)%mod; ll tmp=Pow(a,b/2); return tmp*tmp%mod; } int main() { fast; cin>>n>>m>>k; int u,v; for(int i=1;i<=m;i++) { cin>>u>>v; G[u][v]=1; G[v][u]=1; } for(int i=1;i<=n;i++) { f[1<<(i-1)][i]=1; } int len=(1<<n)-1; for(int i=1;i<=len;i++) { int s; for(int j=1;j<=n;j++) { if(i>>(j-1)&1) { s=j; break; } } for(int j=1;j<=n;j++) { int t=1<<(j-1); if(!(i&t)) continue; for(int k=s+1;k<=n;k++) { int kk=1<<(k-1); if(i&kk) continue; if(G[j][k]) { f[i|kk][k]=(f[i|kk][k]+f[i][j])%mod; } } if(G[j][s]) { int len=__builtin_popcount(i); if(len>=3) { ans[len%k]=(ans[len%k]+f[i][j])%mod; // cout<<i<<' '<<j<<' '<<ans[0]<<' '; } } } } int inv=Pow(2,mod-2); for(int i=0;i<k;i++) { cout<<ans[i]*inv%mod<<' '; } }
POJ2411 Mondriaan's Dream
棋盘覆盖问题，仅能用(1 imes 2)或者(2 imes 1)的骨牌去填充(h imes w)的棋盘。
我们可以把每一行当前是否被覆盖进行状态压缩，用(1)表示已覆盖，(0)表示未覆盖。那么对于每一行而言，可以留出一定的(0)来给下一行覆盖(2 imes 1)的机会。
那么考虑状态转移的条件。首先必须保证之前的行全部被填满，用(j)表示当前行状态，用(k)表示上一行状态，我们需要把上一行中(0)的位置填满，不然之后无论如何都不能做到密铺。其次，在当前行中排除(2 imes 1)的骨牌，剩下的(1)就是(1 imes 2)骨牌的位置，那么就需要保证连续(1)的个数必须为偶数。这里可以进行预处理，存下所有合法的状态。
剩下就是状态转移。当上述条件全部满足时，(f[i][j]=sum f[i-1][k])，初始条件为(f[0][len-1]=1)，其中(len=(1<<w))。
#include<bits/stdc++.h> #define ll long long #define pb push_back #define fast ios::sync_with_stdio(0),cin.tie(0),cout.tie(0) using namespace std; int state[1<<11]; ll f[13][1<<11]; void init() { for(int i=0;i<(1<<11);i++) { state[i]=1; int j=i; int tmp=0; while(j) { if(j%2==1) tmp++; else { if(tmp%2) { state[i]=0; break; } tmp=0; } j/=2; } if(tmp%2) state[i]=0; } } int main() { fast; int h,w; init(); while(cin>>h>>w) { if(h==0 && w==0) break; int len=(1<<w); for(int i=0;i<=h;i++) { for(int j=0;j<len;j++) { f[i][j]=0; } } f[0][len-1]=1; // for(int i=0;i<len;i++) // { // cout<<i<<' '<<state[i]<<' '; // } for(int i=1;i<=h;i++) { for(int j=0;j<len;j++) { for(int k=0;k<len;k++) { if(state[j&k] && (j|k)==len-1) { f[i][j]+=f[i-1][k]; } } } } cout<<f[h][len-1]<<' '; } }