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,代表該數字的位置不被限制。度度熊保證不會為兩個數字指定相同的位置。
Output
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
4600
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<bitset>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
using namespace std;
typedef long long LL;
const int low(int x) { return x&-x; }
const int INF = 0x7FFFFFFF;
const int mod = 1e9 + 7;
const int maxn = 1e5 + 10;
int T, cas = 1;
int n, m;
int x[20], y[20], f[20];
int dp[17][1 << 17][17], c[17][1 << 17][17], ans;
struct point
{
int x, y, z;
point(int x = 0, int y = 0, int z = 0) :x(x), y(y), z(z) {};
};
int main()
{
scanf("%d", &T);
while (T--)
{
scanf("%d", &n);
for (int i = 0; i < n; i++) f[i] = -1;
for (int i = 0; i < n; i++)
{
scanf("%d%d", &x[i], &y[i]);
if (y[i] != -1) f[y[i]] = i;
}
queue<point> p;
if (f[0] == -1)
{
for (int i = 0; i < 16; i++)
{
if (y[i] == -1)
{
p.push(point(0, 1 << i, i));
dp[1][1 << i][i] = 0;
c[1][1 << i][i] = cas;
}
}
}
else
{
p.push(point(0, 1 << f[0], f[0]));
dp[1][1 << f[0]][f[0]] = 0;
c[1][1 << f[0]][f[0]] = cas;
}
ans = -INF;
while (!p.empty())
{
point q = p.front(); p.pop();
if (q.x == n) continue;
if (f[q.x + 1] == -1)
{
for (int i = 0; i < n; i++)
{
if ((1 << i) & q.y || y[i] != -1) continue;
if (c[q.x + 1][q.y ^ (1 << i)][i] != cas)
{
c[q.x + 1][q.y ^ (1 << i)][i] = cas;
dp[q.x + 1][q.y ^ (1 << i)][i] = dp[q.x][q.y][q.z] + x[q.z] * x[i];
p.push(point(q.x + 1, q.y ^ (1 << i), i));
}
else
{
dp[q.x + 1][q.y ^ (1 << i)][i] = max(dp[q.x + 1][q.y ^ (1 << i)][i], dp[q.x][q.y][q.z] + x[q.z] * x[i]);
}
}
}
else
{
int i = f[q.x + 1];
if (c[q.x + 1][q.y ^ (1 << i)][i] != cas)
{
c[q.x + 1][q.y ^ (1 << i)][i] = cas;
dp[q.x + 1][q.y ^ (1 << i)][i] = dp[q.x][q.y][q.z] + x[q.z] * x[i];
p.push(point(q.x + 1, q.y ^ (1 << i), i));
}
else
{
dp[q.x + 1][q.y ^ (1 << i)][i] = max(dp[q.x + 1][q.y ^ (1 << i)][i], dp[q.x][q.y][q.z] + x[q.z] * x[i]);
}
}
}
for (int i = 0; i < n; i++)
{
if (c[n-1][(1 << n) - 1][i] == cas)
{
ans = max(ans, dp[n - 1][(1 << n) - 1][i]);
}
}
printf("Case #%d:\n%d\n", cas++, ans);
}
return 0;
}