2016"百度之星" - 初赛（Astar Round2A）Sitting in Line

Love The Way You Lie 2022-08-22 04:52 171阅读 0赞

之前写状压DP都是用递归写的，感觉递归写好理解，没想到这次递归超时了，没办法，看了一下循环写的状压DP

1.先说一下我对旅行商问题用循环写状压的理解

下面是旅行商问题的核心代码

for(int s=0;s<(1<<n);s++)
            fill(dp[s],dp[s]+n,inf);
        dp[(1<<n)-1][0]=0;
        for(int s=(1<<n)-2;s>=0;s--)
        {
            for(int v=0;v<n;v++)
            {
                for(int u=0;u<n;u++)
                {
                    if(!(s>>u&1)){
                        dp[s][v]=min(dp[s][v],dp[s|1<<u][u]+d[v][u]);
                    }
                }
            }
        }

现在假设有五个点,起点为0

这里dp\[s\]\[v\] s表示已经访问的集合，v表示最后是在哪个点，这里计算了许多不存在的情况。

（1）dp\[10100\]\[1\] 这个状态显然是非法的，因为明明没经过这点怎么可能最后在在这个点  
（2）然后两层循环的时候也会计算一些非法状态，比如dp\[10100\]\[1\] 下面的可到达点u就循环到1，相当于  
dp\[10100\]\[1\] =dp\[10110\]\[1\]+d\[1\]\[1\]  
dp\[10100\]\[1\] =dp\[10110\]\[1\]  
那么 这些非法状态的会影响到最终结果么？答案是不会

首先我们的最后要的答案是dp\[0\]\[0\]，dp\[0\]\[0\]可由下面这几种情况得到

dp\[0\]\[0\] = d\[00001\]\[0\] +d\[0\]\[0\] (1)  
d\[00010\]\[1\] +d\[0\]\[1\] (2)  
d\[00100\]\[2\] +d\[0\]\[2\] (3)  
d\[01000\]\[3\] +d\[0\]\[3\] (4)  
d\[10000\]\[4\] +d\[0\]\[4\] (5)

dp\[00100\]\[2\]可由下面几种情况得到

dp\[00100\]\[2\] = dp\[00101\]\[0\]+d\[0\]\[2\] (6)  
dp\[00110\]\[1\]+d\[1\]\[2\] (7)  
dp\[01100\]\[3\]+d\[2\]\[3\] (8)  
dp\[10100\]\[4\]+d\[2\]\[4\] (9)

可以看出状态1 2 3 4 5 6 7 8 9都是合法的，所以我们DP转移的时候就只会从正确状态转移，同时我们

dp[(1<<n)-1][0]=0

这样赋初值能保证最后一次转移的时候，转移到的点不是第一个点就会是INF，我们不会选取。  
所以非法状态不会影响到最后结果，我们通过赋初值与正确的选取的答案的值、正确的状态转移来抛弃掉非法状态。

2.回归这道题。。

题目链接：[http://acm.hdu.edu.cn/showproblem.php?pid=5691][http_acm.hdu.edu.cn_showproblem.php_pid_5691]

题目大意：给你n个数字，一些数字没有指定位置，一些数字指定了位置，问如何排列这些数字能使最后(a0×a1+a1×a2+a2×a3——  
\+a(n-1)\*a(n) )这个结果最大

题目解析：首先我们要赋初值，首先全部变成-inf，判断最后的位置是否为固定数字，如果固定，则将该数字的输入位置赋值为0，否则将位置不固定的数字的输入位置都赋值成0。

mark\[\]为第几位的数字是否固定，p\[\]为数字的位置。

if(mark[n-1]>=0)
            {
                dp[(1<<n)-1][mark[n-1]]=0;
            }
            else
            {
                for(int i=0; i<n; i++)
                {
                    if(p[i]==-1) dp[(1<<n)-1][i]=0;
                }
            }

timee记录当前乘了几次，它的值为状态数中1的个数减1，当当前次数为固定数字时，则将当前所在的位置固定。  
当当前不为固定数字时，则查找位置不固定的数字进行转移。

假设n为5  
dp\[00001\]\[0\]  
dp\[00010\]\[1\]  
dp\[00100\]\[2\]  
dp\[01000\]\[3\]  
dp\[10000\]\[4\]  
即枚举第一个数字的位置。

这里写代码片

AC代码：

#include <iostream>
    #include <cstring>
    #include <cstdio>
    #include <cstdlib>
    #include <cmath>
    #include <string>
    #include <vector>
    #include <list>
    #include <map>
    #include <queue>
    #include <stack>
    #include <algorithm>
    #include <numeric>
    #include <functional>
    #define RI(N) scanf("%d",&(N))
    #define RII(N,M) scanf("%d %d",&(N),&(M))
    #define RIII(N,M,K) scanf("%d %d %d",&(N),&(M),&(K))
    #define mem(a) memset((a),0,sizeof(a))
    using namespace std;
    
    const int inf=1e9;
    double EPS=1e-10;
    typedef long long LL;
    
    int n,dp[1<<16][20];
    int v1[20];
    int p[20];
    int mark[20];
    
    int cal(int x)
    {
        int anss=0;
        while(x)
        {
            x&=(x-1);
            anss++;
        }
        return anss;
    }
    
    int main()
    {
        int t;
        int tt=1;
        RI(t);
        while(t--)
        {
            RI(n);
            printf("Case #%d:\n",tt++);
            memset(mark,-1,sizeof(mark));
    
            for(int s=0; s<1<<n; s++)
                fill(dp[s],dp[s]+n,-inf);
    
            for(int i=0; i<n; i++)
            {
                int val,poi;
                RII(val,poi);
                v1[i]=val;
                p[i]=poi;
            }
    
            for(int i=0; i<n; i++)
            {
                if(p[i]>=0) mark[p[i]]=i;
            }
    
            if(mark[n-1]>=0)
            {
                dp[(1<<n)-1][mark[n-1]]=0;
            }
            else
            {
                for(int i=0; i<n; i++)
                {
                    if(p[i]==-1) dp[(1<<n)-1][i]=0;
                }
            }
            for(int s=(1<<n)-2; s>=0; s--)
            {
                int timee=cal(s);
                if(timee>=1) timee--;
                else break;
                if(mark[timee]>=0)
                {
                    int v=mark[timee];
                    for(int u=0; u<n; u++)
                    {
                        if(((s>>u)&1)==0)    dp[s][v]=max(dp[s][v],dp[s|(1<<u)][u]+v1[v]*v1[u]);
                    }
                }
                else
                {
                    for(int v=0; v<n; v++)
                    {
                        if(p[v]>=0) continue;
                        for(int u=0; u<n; u++)
                        {
                            if(((s>>u)&1)==0)    dp[s][v]=max(dp[s][v],dp[s|(1<<u)][u]+v1[v]*v1[u]);
                        }
    
                    }
                }
            }
            int ans=-inf;
            for(int i=0;i<n;i++)
            {
                ans=max(ans,dp[1<<i][i]);
            }
            printf("%d\n",ans);
    
    
        }
        return 0;
    }

[http_acm.hdu.edu.cn_showproblem.php_pid_5691]: http://acm.hdu.edu.cn/showproblem.php?pid=5691