題目連接：
http://acm.hdu.edu.cn/showproblem.php?pid=5691
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
Hint
題意
題解：
狀壓dp
dp[i][j]表示狀態為i的時候，最后一個是j的最大值
然后直接轉移就好了，現在他是第幾個，就是前面有多少個1就好了
這個可以預處理出來
代碼
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <conio.h>using namespace std;const int maxn = 16;
const int inf = 2e9;int dp[1 << 16][17];int p[maxn] , N , a[maxn] , counter[1 << 16];inline void Update( int & x , int v ){x = max( x , v );
}int main(){int Case , cas = 0;scanf("%d",&Case);for(int i = 0 ; i < ( 1 << 16) ; ++ i) counter[i] = __builtin_popcount(i);while(Case--){scanf("%d",&N);for(int j = 0 ; j < ( 1 << N ) ; ++ j ) for(int k = 0 ; k <= N ; ++ k) dp[j][k] = -inf;for(int i = 0 ; i < N ; ++ i){scanf("%d%d" , a + i , p + i );}a[N] = 0;dp[0][N]=0;for(int i = 0 ; i < ( 1 << N) ; ++ i)for(int j = 0 ; j <= N ; ++ j)if( dp[i][j] != - inf )for(int v = 0 ; v < N ; ++ v)if( ( (i >> v & 1) == 0) && ( p[v] == -1 || p[v] == counter[i] ) )Update( dp[i | ( 1 << v )][ v ] , dp[i][j] + a[j] * a[v] );int ans = -inf;for(int i = 0 ; i <= N ; ++ i ) Update( ans , dp[ (1<<N)-1 ][i] );printf("Case #%d:\n" , ++ cas);printf("%d\n" , ans);}return 0;
}
