滚粗辣
4
30
2016
30
2016
专题：状态压缩动态规划
再不切题就要退役辣，学习老板娘板切专题。
| BZOJ | 1087 | 1076 | 2064 | 1725 | 1231 | 1688 | 1072 | 1097 | 2734 | 1226 | 2595 | 2073 | 2004 | 2669 |
| CODEVS | 1050 | 2800 | 1358 | 1480 | 2009 | 2017 | 2125 | 2743 | 2818 | 2889 | 2941 | 3122 | 3196 | |
| hdu | 3001 | 3681 | 4114 | 4892 | 4284 | 1074 | 3182 | 4568 | 4336 | 1565 | 2167 | 4539 |
BZOJ：
1087：在N*N的棋盘上放K个互不攻击的王的方案数。
正确姿势：打表233
f[i][j][S]表示第i行状态为S时还剩下j个王可放。位运算预处理一下转移什么的轻易AC了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 | #include<cstdio>#include<cstdlib>#include<cstring>#include<algorithm>#define maxn 10#define maxk 82#define maxS 512using namespace std;int n,k,S;long long f[maxn][maxk][maxS],cnt[maxS],ans;int main(){ scanf("%d%d",&n,&k);S=1<<n; for(int i=0;i<S;i++)if(!(i&(i<<1))) for(int x=i;x;x>>=1)cnt[i]+=(x&1); f[0][k][0]=1; for(int i=1;i<=n;i++) for(int x=1;x<=k;x++) for(int s=0;s<S;s++) for(int t=0;t<S;t++) if(!(s&t)&&!(s&(s<<1))&&!(t&(t<<1))&&!(s&(t<<1))&&!(t&(s<<1))&&cnt[t]<=x) f[i][x-cnt[t]][t]+=f[i-1][x][s]; for(int i=1;i<=n;i++) for(int s=0;s<S;s++) ans+=f[i][0][s]; printf("%lld",ans);} |
1725：
棋盘的给定位置上放置不相邻旗子的方案数。
比上一题还要斯波，f[i][S]表示第i行状态为j的方案数。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | #include<cstdio>#include<cstring> #define MO 100000000using namespace std;int n,m,s[13],f[13][4096],x,ans;int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)scanf("%d",&x),s[i]=(s[i]<<1)+x; int S=1<<m; for(int i=0;i<S;i++)if(!(i&(i<<1))&&(i|s[1])==s[1]) f[1][i]=1; for(int i=2;i<=n;i++) for (int l=0;l<S;l++)if(f[i-1][l]) for(int r=0;r<S;r++) if(!(l&r)&&!(r&(r<<1))&&(r|s[i])==s[i]) f[i][r]=(f[i][r]+f[i-1][l])%MO; for(int i=0;i<S;i++) ans=(ans+f[n][i])%MO; printf("%d",ans);} |
CODEVS：
1050：轮廓线状压DP，详见http://scarlet.is-programmer.com/posts/181697.html
hdu：
3001:
每个点经过不超过两次的TSP。f[i][S]表示经过点的状态S时，最后一个点为i的最小费用。这里S三进制状压，表示每个点已经遍历的次数。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 | #include<cstdio>#include<cstring>#include<algorithm>#define maxn 11#define maxS 59049#define AE(u,v,w) E[Si]=(Ed){v,w},nxt[Si]=idx[u],idx[u]=Si++#define mi(a,b) a=min(a,b)using namespace std;struct Ed{int v,w;}E[maxS];int f[maxn][maxS],n,m,idx[maxn],nxt[maxS],trn[maxn],Si,u,v,w,S,tri[maxS][maxn],c[maxS];int main(){ trn[0]=1;for(int i=1;i<=10;i++)trn[i]=trn[i-1]*3; for(int i=0;i<maxS;i++)for(int j=0,x=i;j<=10;j++,x/=3)tri[i][j]=x%3,c[i]+=((x%3)!=0); while(scanf("%d%d",&n,&m)==2) { Si=0;S=trn[n]; memset(idx,-1,sizeof(idx)); memset(f,0x7f7f7f7f,sizeof(f)); int ans=f[0][0],INF=f[0][0]; for(int i=1;i<=m;i++)scanf("%d%d%d",&u,&v,&w),u--,v--,AE(u,v,w),AE(v,u,w); for(int i=0;i<n;i++)f[i][trn[i]]=0; for(int s=0;s<S;s++) for(int u=0;u<n;u++)if(tri[s][u]!=0) for(int i=idx[u];i+1;i=nxt[i])if(tri[s][E[i].v]<2) mi(f[E[i].v][s+trn[E[i].v]],f[u][s]+E[i].w); for(int s=0;s<S;s++)if(c[s]==n) for(int i=0;i<n;i++) ans=min(ans,f[i][s]); if(ans!=INF)printf("%d\n",ans); else puts("-1"); }} |
