题解 CF8C 【Looking for Order】

Prurite · 2018-04-03 21:25:35 · 题解

建议一层一层地阅读，只在实在想不出来的时候再看下一层。

基本思路

状压DP。以当前已经取了哪些物品作为状态。

主要思路

拿到题， n<=24 的数据范围和512MB的空间限制基本上就标志着这道题是一个标准的状压。为了节省空间，我们就 1<<i-1 表示第 i 个物品有无被取过。由于一次可以选择拿一个或者两个物品，考虑在状态转移的时候枚举这次拿的两个物品（如果两个物品相同就处理为这次只拿一个）。由于要输出拿的方法，我们就再用一个数组记录当前状态是从之前的哪个状态转移过来的即可。

需要注意的是，可以证明，若设每次离开手提包捡拾物品为一次，则各次之间的顺序不影响最终答案。如，第一次拿物品1，第二次拿物品2,3与第一次拿物品2,3，第二次拿物品1的所用时间是一样的。这样，我们在转移的时候就从编号小的物品向编号大的物品找寻，只要找到了当前的一种可用方案就可以进入下一个状态了，这样可以节省时间（同时避免重复计算）。

代码实现

用dis数组表示两点之间的距离，用dp数组表示当前状态下所需的最小时间，用pre数组表示当前状态的来路（从哪个状态转移过来的）。 状态转移方程：顺推，

输出的时候从 pre[(1<<n-1)-1] 往前逆推即可。

代码

#include <stdio.h>

const int MAXN=24, INF=2e9;
struct obj
{
    int x, y;
} things[MAXN+1];
int n;
int dp[1<<MAXN|1], pre[1<<MAXN|1];
int dis[MAXN+1][MAXN+1];

inline void reset( );   //重置数组 
inline void read( );    //读入数据 
inline void init( );    //预处理 
inline void solve( );   //解决 
inline void output( );  //输出 

inline int min( int a, int b ) { return a<b?a:b; }

int main( )
{
    reset( );
    read( );
    init( );
    solve( );
    output( );
    return 0;
} //疯狂的主程序

inline void reset( )
{
    for ( register int i=0; i<=(1<<MAXN); i++ )
        dp[i]=INF, pre[i]=0;
    return;
}

inline void read( )
{
    scanf( "%d %d", &things[0].x, &things[0].y ); //用0表示手提包
    scanf( "%d", &n );
    for ( register int i=1; i<=n; i++ )
        scanf( "%d %d", &things[i].x, &things[i].y );
    return;
}

inline void init( )
{
    for ( register int i=0; i<=n; i++ )
        for ( register int j=0; j<=n; j++ )
            dis[i][j]=dis[j][i]=
            (things[i].x-things[j].x)*(things[i].x-things[j].x)+
            (things[i].y-things[j].y)*(things[i].y-things[j].y);
    return;
}

inline void solve( )
{
    dp[0]=0, pre[0]=0;
    for ( int m=0; m<(1<<n); m++ ) //m为当前处理的状态
    {
        if ( dp[m]==INF )
            continue; //如果当前状态没有被更新过直接continue 
        for ( int i=1; i<=n; i++ )  
        {
            if ( m&1<<i-1 )
                continue;
            for ( int j=1; j<=n; j++ )
            {
                if ( m&1<<j-1 )
                    continue;
                if ( dp[m|(1<<i-1)|(1<<j-1)]>dp[m]+dis[0][i]+dis[i][j]+dis[j][0] )
                    dp[m|(1<<i-1)|(1<<j-1)]=dp[m]+dis[0][i]+dis[i][j]+dis[j][0],
                    pre[m|(1<<i-1)|(1<<j-1)]=m; //状态转移 
            }
            break; //只要找到了一种可行的方案，无论是否转移成功都可以break了 
        }
    }
    return;
}

inline void output( )
{
    printf( "%d\n", dp[(1<<n)-1] );
    int now=(1<<n)-1; //从所有都齐的状态开始逆推
    while ( now!=0 )
    {
        printf( "0 " ); 
        int update=now^pre[now];
        for ( int i=1; i<=n; i++ )
            if ( update&1<<i-1 )
                printf( "%d ", i ); //输出本次拿的哪些物品
        now=pre[now];
    }
    printf( "0\n" );
    return;
}

提交记录 用时: 2346ms / 内存: 134580KB