难度：估计在普及+
        天津大学OJ上的一道题，最早来自The 7th UESTC Programming Contest Preliminary。看rank list发现这道题都做的特别惨烈…一看这题感觉是状压DP，一写果然A了，在这里做一个总结。之后应该还会有类似的情景。
        原题在http://acm.tju.edu.cn/toj/vcontest/showp10518_B.html ，下面是翻译。

题目描述

        上周，应用数学学院举办了放风筝比赛，参赛者分成两组，一对选手与另一名参赛者竞争。众所周知，划分对的不同方式可能带来不同的精彩等级值，精彩等级值是一个数。现在，叶小姐想知道如何划分竞争对手，以达到最高的精彩等级。

输入输出格式

输入格式:

        输入的第一行包含一个整数T，表示测试样例的数量。
        对于每个测试样例，在第一行中有一个整数N(N≤16，N总是偶数)，表示有N名参赛者参加比赛。
        在下一个N行中，每行包含N个数。当第i个选手和第j个常数在一对中进行时，第i行中的第j个数是对应的精彩等级值。数据保证第i行中的第j个数等于第j行中的第i个数，即输入的矩阵是对称的。

输出格式:

        对于每种情况，输出最大的精彩等级值，保留两位小数。

输入输出样例

Sample input

1
2
0.0 1.0
1.0 0.0

Sample output

1.00

题解

        考察状态压缩DP(状压DP)，这是继离散化，压缩数组等DP技巧后的又一个重要方法。
        状态压缩DP是指用二进制编码的方法记录状态。这类的问题通常状态很多，但个体总数是不大的，比如本题小于16。这时可以用一个16位二进制数的01序列顺序来记录这些状态。
        如果对于一个二进制数x，用第i位为0表示第i+1个人未被安排，为1表示已被安排。f(x)表示在此情况下所得的最大精彩等级值，那么有状态转移方程：

        n表示总人数。答案即为f(0)。
        实际操作中，可以发现每一对的安排顺序是无所谓的，只要确定了一对(a，b)，这一次状态转移只需改变b的值即可，无需再改变a。这样可以保证加入的数对序列中a是递增的且总有a < b，从而避免很多本质相同的序列组合，大大节约时间，这就是自排序原则的应用。
        附自排序原则的泛化描述:当序列的顺序不重要时(主要针对集合)，我们用一种特定的顺序(可以按排序顺序也可按输入顺序)构造或访问这个序列，从而避免大量排列不同但本质相同的组合。这种重要思想称为自排序原则。它有很多应用，比如背包问题属于按输入顺序排序，本题按a升序排序，都能节省时间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<iostream>
#include<iomanip>

using namespace std;
int n;
double op[16][16], dp[1 << 18];

double DP(int x) {
    double ans = 0.0;
    if (dp[x] >= 0.0)return dp[x];
    for (int i = 0; i < n; i++) {
        if ((x & (1 << i)) != 0)continue;
        for (int j = i + 1; j < n; j++) {
            if ((x & (1 << j)) == 0)ans = max(ans, op[i][j] + DP(x | (1 << i) | (1 << j)));
        }
        break;
    }
    return dp[x] = ans;
}

int main() {
    ios::sync_with_stdio(false);
    int T;
    cin >> T;
    for (int t = 0; t < T; t++) {
        cin >> n;
        int temp = (1 << n);
        for (int i = 0; i < temp; i++)dp[i] = -1.0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++)cin >> op[i][j];
        }
        cout << setiosflags(ios::fixed) << setprecision(2) << DP(0) << endl;
    }
}