hdu5691(状态压缩dp)Sitting in Line

2017年08月03日 9点热度 0人点赞 0条评论

Sitting in Line

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 1145    Accepted Submission(s): 547

Problem Description
度度熊是他同时代中最伟大的数学家,一切数字都要听命于他。现在,又到了度度熊和他的数字仆人们玩排排坐游戏的时候了。游戏的规则十分简单,参与游戏的N个整数将会做成一排,他们将通过不断交换自己的位置,最终达到所有相邻两数乘积的和最大的目的,参与游戏的数字有整数也有负数。度度熊为了在他的数字仆人面前展现他的权威,他规定某些数字只能在坐固定的位置上,没有被度度熊限制的数字则可以自由地交换位置。
Input
第一行一个整数T,表示T组数据。
每组测试数据将以如下格式从标准输入读入:

N

a1p1

a2p2

aNPN

第一行,整数 N(1N16),代表参与游戏的整数的个数。

从第二行到第 (N+1) 行,每行两个整数,ai(10000ai10000)pi(pi=1 或 0pi<N),以空格分割。ai代表参与游戏的数字的值,pi代表度度熊为该数字指定的位置,如果pi=1,代表该数字的位置不被限制。度度熊保证不会为两个数字指定相同的位置。

 

Output
第一行输出:"Case #i:"。i代表第i组测试数据。

第二行输出数字重新排列后最大的所有相邻两数乘积的和,即max{a1a2+a2a3+......+aN1aN}

 

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
#include
#include
#include
using namespace std;
const int INF=1e9;
int n,a[20],p[20],f[1<<16][20];
int main(){
	int T,kase=0;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);
		for(int i=0;i
未经允许不得转载!hdu5691(状态压缩dp)Sitting in Line

update

纸上得来终觉浅, 绝知此事须躬行。