11
8
2016
8
2016
NOIP泛做
NOIP泛做
联赛前没心情做BZOJ跑来写联赛题解23333
点击题目名称前往题目页面查看题目
年份我选择倒序= =
发现数学公式显示[Math Processing Error]的选手请右键任一公式,点击
Math Settings->Math Renderer->重新选择HTML-CSS即可正常显示公式
觉得阅读难受的不妨试试标导航栏上的同名链接
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了。
#include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> #define maxn 10 #define maxk 82 #define maxS 512 using 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的方案数。
#include<cstdio> #include<cstring> #define MO 100000000 using 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三进制状压,表示每个点已经遍历的次数。
#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"); } }