Sitting in Line
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 597 Accepted Submission(s): 274
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，代表该数字的位置不被限制。度度熊保证不会为两个数字指定相同的位置。
每组测试数据将以如下格式从标准输入读入：
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}。
第二行输出数字重新排列后最大的所有相邻两数乘积的和，即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
解题思路：状态压缩。用dp[i][j]表示选择i状态所表示的数时，以第j个数为结尾时的最大和。转移方程: dp[i|(1<<k)][k] = max(dp[i|(1<<k)][k], dp[i][j] + a[i]*a[j])。
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<math.h>
#include<string>
#include<iostream>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#include<set>
using namespace std;
typedef long long LL;
#define mid (L+R)/2
#define lson rt*2,L,mid
#define rson rt*2+1,mid+1,R
#pragma comment(linker, "/STACK:102400000,102400000")
const int maxn = 1e5+300;
const LL INF = 1000000000000;
typedef long long LL;
typedef unsigned long long ULL;
int a[30], p[30];
int choice[maxn];
LL dp[maxn][30];
int cal(int x){
int ret = 0;
while(x){
if(x&1)
ret++;
x = x>>1;
}
return ret;
}
int main(){
int T, n, cas = 0;
scanf("%d",&T);
//预处理出来数字i二进制中有多少个1，因为在有定位置的数时，需要保证前面有那么多个1
for(int i = 0; i <= (1<<16); i++){
choice[i] = cal(i);
}
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;
}
}
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 k = 0; k < n; k++){
if((i&(1<<k)) == 0&&(p[k] == -1 || p[k] == choice[i])){
dp[i|(1<<k)][k] = max(dp[i|(1<<k)][k],dp[i][j] + a[j]*a[k]);
}
}
}
}
}
LL ans = -INF;
for(int i = 0; i < n; i++){
ans = max(ans, dp[(1<<n)-1][i]);
}
printf("Case #%d:
",++cas);
printf("%lld
",ans);
}
return 0;
}