menu ZigZagK的博客

正在努力加载中QAQ

[状压DP]NOIP2017Day2【宝藏】题解
apps HHHOJ
local_offer 查看标签
comment 0 条评论
remove_red_eye 23 次访问

解题报告

吃我一记万年神坑。去年考场上做这题的时候一直在想二进制状压,现在回头看看那时候的自己真是蠢爆了。

很明显可以三进制状压 $f_{i,s}$ 表示深度为 $i$ 时,每个点的状态 $0/1/2$ 表示没选/上一层/这一层,转移很显然。

但是这样复杂度上天了,三进制状压让我们意识到一件事情:子集枚举。每次对于一个二进制状态,我们枚举他的子集表示之前选的状态,那么多出来的就是这一层的点。

不过仔细想想就会发现很奇怪,如何保证这一层的点连向上一层的点而不是之前层的点?其实最小值已经保证了这个性质,如果某个点没有连向上一层,那么说明他不是这层的点,但统计答案的时候一视同仁导致该点多统计了,这不会出现在最优解中。

直接做是 $O(3^nn^3)$ 的,预处理一下就可以做到 $O(3^nn)$ 。

示例程序

注意刷最优解时候的边界……否则可能会被 $n=1$ 卡……

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=12,maxs=1<<maxn;

int n,m,INF,dis[maxn+5][maxn+5],f[maxn+5][maxs],MIN[maxn+5][maxs],g[maxs][maxs];

int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d%d",&n,&m);memset(dis,63,sizeof(dis));INF=dis[0][0];
    for (int i=1,x,y,z;i<=m;i++) scanf("%d%d%d",&x,&y,&z),x--,y--,dis[x][y]=dis[y][x]=min(dis[x][y],z);
    memset(f,63,sizeof(f));for (int i=0;i<n;i++) f[0][1<<i]=0;memset(MIN,63,sizeof(MIN));
    for (int s=1;s<(1<<n);s++)
        for (int i=0;i<n;i++)
            for (int j=0;j<n;j++)
                if (s>>j&1) MIN[i][s]=min(MIN[i][s],dis[i][j]);
    for (int S=1;S<(1<<n);S++)
        for (int s=S-1&S;s;s=s-1&S)
            for (int j=0;j<n;j++)
                if ((S>>j&1)&&!(s>>j&1))
                    if (MIN[j][s]<INF) g[S][s]+=MIN[j][s]; else {g[S][s]=INF;break;}
    for (int i=1;i<=n;i++)
        for (int S=1;S<(1<<n);S++)
            for (int s=S-1&S;s;s=s-1&S)
                if (f[i-1][s]<INF&&g[S][s]<INF) f[i][S]=min(f[i][S],f[i-1][s]+g[S][s]*i);
    int ans=INF;for (int i=0;i<=n;i++) ans=min(ans,f[i][(1<<n)-1]);printf("%d\n",ans);return 0;
}
版权声明:本博客所有文章除特别声明外,均采用 CC BY 4.0 CN协议 许可协议。转载请注明出处!
名称不能为空
邮箱不能为空,请填写正确格式
网址请用http://或https://开头
评论不能为空
资瓷Markdown和LaTex数学公式
keyboard_arrow_up