CF8C Looking for Order

CodeForces

Luogu

算法

此题数据范围很小,且空间限制很大。所以考虑状压DP。

设$f[S]$表示到状态$S$走的最小距离。显然边界为$f[0]=0$。

每次枚举两个点$i$、$j$($i$可以等于$j$),可以得到状态转移方程:

$f[S|(1<<i-1)|(1<<j-1)]=min(f[S|(1<<i-1)|(1<<j-1)],f[S]+dis[0][i]+dis[i][j]+dis[j][0])$

最后答案为$f[(1<<n)-1]$。

注意到,每次去取东西的顺序对答案没有影响。

所以转移后直接break即可。

在DP时记录$pre$数组,利用异或递归输出即可。

代码

#include <bits/stdc++.h>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
    return X*w;
}

int dis[30][30];
int x[30],y[30];
int n;

int f[1<<24|1],pre[1<<24|1];

inline void Print(int S) {
    if (S==0) return;
    Print(pre[S]);
    int k=S^pre[S];
    printf("0 ");
    for (re int i=1;i<=n;i++)
        if (k&(1<<i-1)) printf("%d ",i);
}

int main() {
    x[0]=read(),y[0]=read();
    n=read();
    for (re int i=1;i<=n;i++) x[i]=read(),y[i]=read();
    
    for (re int i=0;i<=n;i++)
        for (re int j=0;j<=n;j++)
            dis[i][j]=(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]);
    
    memset(f,0x3f,sizeof(f));
    f[0]=0,pre[0]=0;
    for (re int S=0;S<(1<<n);S++) {
        if (f[S]==0x3f3f3f3f) continue;
        for (re int i=1;i<=n;i++) {
            if (S&(1<<i-1)) continue;
            for (re int j=1;j<=n;j++) {
                if (S&(1<<j-1)) continue;
                if (f[S]+dis[0][i]+dis[i][j]+dis[j][0]<f[S|(1<<i-1)|(1<<j-1)]) {
                    f[S|(1<<i-1)|(1<<j-1)]=f[S]+dis[0][i]+dis[i][j]+dis[j][0];
                    pre[S|(1<<i-1)|(1<<j-1)]=S;
                }
            }
            break;
        }
    }
    
    printf("%d\n",f[(1<<n)-1]);
    Print((1<<n)-1); printf("0\n");
    
    return 0;
}
最后修改:2019 年 09 月 24 日 01 : 10 PM

发表评论