HDU 5691(动态规划-状压dp)

古城微笑少年丶 2022-06-01 10:24 201阅读 0赞

问题描述:

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

Input

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

Output

第一行输出："Case \#i:"。ii代表第ii组测试数据。

第二行输出数字重新排列后最大的所有相邻两数乘积的和，即

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

题目分析:dp\[i\]\[j\],表示在状态i情况下，最后一个是p\[j\]的最大值，对于p\[j\]=-1的比较好处理，因为它可以放到任意地方，而不等于-1的就得判断一下，是否可以放。因为如果旁边没有放的话。那么值就为0.

代码如下:

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<cmath>
    using namespace std;
    
    const int inf=0x3f3f3f3f;
    const int maxn=20;
    int a[maxn],p[maxn];
    int dp[1<<17][maxn];
    
    int main()
    {
        int t,n;
        scanf("%d",&t);
        for (int icase=1;icase<=t;icase++) {
            scanf("%d",&n);
            for (int i=1;i<=n;i++) {
                scanf("%d%d",&a[i],&p[i]);
            }
            for (int i=0;i<(1<<n);i++) {
                for (int j=0;j<=n;j++) {
                    dp[i][j]=-inf;
                }
            }
            a[0]=dp[0][0]=0;
            for (int i=0;i<(1<<n);i++) {
                for (int j=0;j<=n;j++) {
                    if (dp[i][j]==-inf) continue;
                    for (int k=1;k<=n;k++) {
                        if (i&(1<<(k-1))) continue;
                        if (p[k]==-1) {
                            dp[i|(1<<(k-1))][k]=max(dp[i|(1<<(k-1))][k],dp[i][j]+a[j]*a[k]);
                        }
                        else {
                            int cnt=0;
                            for (int l=0;i>=(1<<l);l++) if ((1<<l)&i) cnt++;
                            if (cnt!=p[k]) continue;
                            dp[i|(1<<(k-1))][k]=max(dp[i|(1<<(k-1))][k],dp[i][j]+a[j]*a[k]);
                        }
                    }
                }
            }
            int ans=-inf;
            for (int i=1;i<=n;i++) {
                ans=max(ans,dp[(1<<n)-1][i]);
            }
            printf("Case #%d:\n",icase);
            printf("%d\n",ans);
        }
        return 0;
    }