hdu 5691 Sitting in Line 状态压缩dp

川长思鸟来 2022-07-24 12:29 161阅读 0赞

# Sitting in Line #

**Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)  
Total Submission(s): 580    Accepted Submission(s): 264**

Problem Description

度度熊是他同时代中最伟大的数学家，一切数字都要听命于他。现在，又到了度度熊和他的数字仆人们玩排排坐游戏的时候了。游戏的规则十分简单，参与游戏的N个整数将会做成一排，他们将通过不断交换自己的位置，最终达到所有相邻两数乘积的和最大的目的，参与游戏的数字有整数也有负数。度度熊为了在他的数字仆人面前展现他的权威，他规定某些数字只能在坐固定的位置上，没有被度度熊限制的数字则可以自由地交换位置。

Input

第一行一个整数 T，表示 T组数据。  
每组测试数据将以如下格式从标准输入读入：  
  
N  
  
a1p1  
  
a2p2  
  
:    
  
aNPN  
  
第一行，整数   N(1≤N≤16)，代表参与游戏的整数的个数。  
  
从第二行到第   (N\+1)  行，每行两个整数， ai(−10000≤ai≤10000)、 pi(pi=−1  或   0≤pi<N)，以空格分割。 ai代表参与游戏的数字的值， pi代表度度熊为该数字指定的位置，如果 pi=−1，代表该数字的位置不被限制。度度熊保证不会为两个数字指定相同的位置。

Output

第一行输出："Case \#i:"。 i代表第 i组测试数据。  
  
第二行输出数字重新排列后最大的所有相邻两数乘积的和，即 max\{ a1⋅a2\+a2⋅a3\+......\+aN−1⋅aN\}。

Sample Input

2
    6
    -1 0
    2 1
    -3 2
    4 3
    -5 4
    6 5
    5
    40 -1
    50 -1
    30 -1
    20 -1
    10 -1

Sample Output

Case #1:
    -70
    Case #2:
    4600

Source

[2016"百度之星" - 初赛（Astar Round2A）][2016_ - _Astar Round2A]

Recommend

wange2014

题意: 给定n个数, 让你选择一个序列, 使得这个序列中相邻的两个数乘积之和最大;

分析: 看见n是16, 就能自然联想到状态压缩dp了, 很遗憾开始理解错了题目, 一直在瞎写....

将所有数的状态压缩之后, 就可以在这基础上进行dp了, 可以看到这个dp是与顺序有关的, 我们要多加一维用来表示最后一个添加的元素. 即dp\[i\]\[j\]表示在i状态的情况下最后一个添加的是j位置的元素的最大值.

我们遍历所有的状态, 对于每一种状态, 统计里面1的个数为num, 说明这种状态中已经有num个数了, 下面我们需要添加第num+1个数, 我们遍历i状态的最后一个添加的元素, 然后枚举能添加的元素, 把i状态能够转移到的状态进行更新,当然这要判断一下添加第num+1个数的时候是不是必须固定位置, 如果是固定位置的话就直接转移就行啦.

#include<bitset>
    #include<map>
    #include<vector>
    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<string>
    #include<algorithm>
    #include<cmath>
    #include<stack>
    #include<queue>
    #include<set>
    #define inf 0x3f3f3f3f
    #define mem(a,x) memset(a,x,sizeof(a))
    #define F first
    #define S second
    using namespace std;
    
    typedef long long ll;
    typedef pair<int,int> pii;
    
    inline int in()
    {
        int res=0;char c;int f=1;
        while((c=getchar())<'0' || c>'9')if(c=='-')f=-1;
        while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();
        return res*f;
    }
    const int N=100010,MOD=1e9+7;
    int a[16];
    int dp[1<<16][16],must[16];
    int one[1<<16];
    
    int main()
    {
        for(int i=0;i<1<<16;i++){
            for(int j=i;j;j>>=1) one[i] += j&1;
        }
        int T=in(),ca=1;
        while(T--)
        {
            int n=in();
            mem(must,-1);
            int x,y;
            for(int i=0;i<n;i++){
                scanf("%d%d",&x,&y);
                a[i]=x;
                if(y != -1) must[y]=i;  //y位置必须是ai值
            }
            int all=1<<n;
    
            for(int i=0;i<all;i++){
                for(int j=0;j<n;j++){
                    dp[i][j] = -inf;
                }
            }
            //0没法转移, 特殊处理
            if(must[0] == -1){
                for(int i=0;i<n;i++){
                    dp[1<<i][i]=0;
                }
            }
            else{
                dp[1<<must[0]][must[0]]=0;
            }
            for(int i=1;i<all;i++){
                int num=one[i];
                if(must[num] == -1){
                    for(int j=0;j<n;j++){  //枚举结束位置
                        if(i&1<<j && dp[i][j] != -inf){
                            for(int k=0;k<n;k++){  //枚举下一次加的值
                                if(!(i&1<<k)){
                                    dp[i|1<<k][k] = max(dp[i|1<<k][k],dp[i][j]+a[k]*a[j]);
                                }
                            }
                        }
                    }
                }
                else{
                    int k=must[num];  //下一个位置必须是a[k]
                    if(i&1<<k) continue; //如果a[k]已经使用, 不更新
                    for(int j=0;j<n;j++){
                        if(i&1<<j && dp[i][j] != -inf){
                            dp[i|1<<k][k] = max(dp[i|1<<k][k],dp[i][j]+a[j]*a[k]);
                        }
                    }
                }
            }
            int ans=-inf;
            for(int j=0;j<n;j++) ans = max(ans,dp[all-1][j]);
            printf("Case #%d:\n%d\n",ca++,ans);
        }
        return 0;
    }

[2016_ - _Astar Round2A]: http://acm.hdu.edu.cn/search.php?field=problem&key=2016%26quot%3B%B0%D9%B6%C8%D6%AE%D0%C7%26quot%3B+-+%B3%F5%C8%FC%A3%A8Astar+Round2A%A3%A9&source=1&searchmode=source