题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5691
题意：
给定n个数, 让你选择一个序列, 使得这个序列中相邻的两个数乘积之和最大。
解法：
状压DP。将所有数的状态压缩之后, 就可以在这基础上进行dp了, 可以看到这个dp是与顺序有关的, 我们要多加一维用来表示最后一个添加的元素. 即dp[i][j]表示在i状态的情况下最后一个添加的是j位置的元素的最大值.
我们遍历所有的状态, 对于每一种状态, 统计里面1的个数为num, 说明这种状态中已经有num个数了, 下面我们需要添加第num+1个数, 我们遍历i状态的最后一个添加的元素, 然后枚举能添加的元素, 把i状态能够转移到的状态进行更新,当然这要判断一下添加第num+1个数的时候是不是必须固定位置, 如果是固定位置的话就直接转移就行啦.

//HDU 5691

#include <bits/stdc++.h>
using namespace std;
const int maxn = 16;
const int inf = 0x3f3f3f3f;
int dp[1<<16][17]; //状态为i，最后一个数为a[j]的最大值
int a[17], p[17];
int main(){
    int T, n, ks = 0;
    scanf("%d", &T);
    while(T--){
        scanf("%d", &n);
        for(int i = 0; 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;
            }
        }
        for(int i = 0; i < n; i++){//只有p[i]=0或者p[i]=-1时才能初始化
            if(p[i] == 0 || p[i] == -1) dp[1<<i][i] = 0;
        }
        for(int i = 0; i < (1<<n); i++){
            for(int j = 0; j < n; j++){
                if(dp[i][j] != -inf){//当是第p[k]个或者p[k]是-1时才能继续往里放
                    for(int k = 0; k < n; k++){
                        if(((1<<k)&i) == 0 && ((p[k] == __builtin_popcount(i)) || p[k] == -1)){
                            dp[i|(1<<k)][k] = max(dp[i|(1<<k)][k], dp[i][j]+a[j]*a[k]);
                        }
                    }
                }
            }
        }
        int ans = -inf;
        for(int i = 0; i < n; i++){
            ans = max(ans, dp[(1<<n)-1][i]);
        }
        printf("Case #%d:\n", ++ks);
        printf("%d\n", ans);
    }
    return 0;
}