傳送門

Sitting in Line

Time Limit: 10000/5000 MS (Java/Others)????Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 293????Accepted Submission(s): 143

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 第一行輸出："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

?

Source 2016"百度之星" - 初賽（Astar Round2A）

?

Recommend wange2014???|???We have carefully selected several similar problems for you:??5695?5694?5693?5692?5690? 題意： 數組中有些元素位置被固定了，有些可以換位置，求 max{a1?a2+a2?a3+......+aN?1?aN} 題解： 真不容易，田神給我說了思路，還編了好久2333

狀壓dp，比賽時沒時間思考了。。。

其實，觀察所要求的max{a1?a2+a2?a3+......+aN?1?aN}

可以發現，你發完前 i - 1 位 元素后，準備放第 i 位 元素時，當前的 max 只 與 a[i-1] 有關了 （a[i - 1] * a[i]），所以可以用狀壓dp

定義 dp[o][i] 為放完第i位（以a[i] 為結尾），狀態 o 時的max

?

遍歷的順序見代碼

?

17232841

2016-05-21 22:22:30

Accepted

5691

1294MS

11724K

2946B

G++

czy

?

1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cstring> 5 #include <algorithm> 6 #include <vector> 7 8 using namespace std; 9 10 #define N 19 11 #define ll long long 12 13 ll ma; 14 ll a[N]; 15 int p[N]; 16 int have[N]; 17 int n; 18 ll dp[ (1 << 17) ][N]; 19 int tot; 20 ll inf; 21 vector<int> G[N]; 22 23 int cal(int x) 24 { 25 int ret = 0; 26 while(x){ 27 ret += (x & 1); 28 x /= 2; 29 } 30 return ret; 31 } 32 33 void ini() 34 { 35 int o; 36 for(o = 0;o < n;o++){ 37 G[o].clear(); 38 } 39 for(o = 0;o < tot;o++){ 40 G[ cal(o) ].push_back(o); 41 } 42 } 43 44 int main() 45 { 46 47 int T; 48 //freopen("in.txt","r",stdin); 49 //freopen("out.txt","w",stdout); 50 scanf("%d",&T); 51 for(int ccnt = 1;ccnt <= T;ccnt++){ 52 scanf("%d",&n); 53 inf = (1LL << 60); 54 ma = -inf; 55 tot = (1 << n); 56 ini(); 57 int i; 58 memset(have,-1,sizeof(have)); 59 for(i = 0;i < n;i++){ 60 scanf("%I64d%d",&a[i],&p[i]); 61 if(p[i] != -1){ 62 have[ p[i] ] = i; 63 } 64 } 65 int o,nt; 66 for(o = 0;o < tot;o++){ 67 for(i = 0;i < n;i++){ 68 dp[o][i] = -inf; 69 } 70 } 71 for(i = 0;i < n;i++){ 72 if(p[i] == 0 || p[i] == -1){ //放在第一個 73 dp[ (1 << i) ][i] = 0; 74 } 75 } 76 77 /* 78 for(i = 0;i < n;i++){ 79 for(int j = 0;j < G[i].size();j++){ 80 printf(" i =%d j = %d g= %d\n",i,j,G[i][j]); 81 } 82 }*/ 83 for(i = 1;i < n;i++){ //放第i位 84 int sz = G[i].size(); 85 for(int j = 0;j < sz;j++){ //遍歷含有i個1的所有數 86 o = G[i][j]; 87 for(int k = 0;k < n;k++) //把第k個數放在第i位 88 { 89 90 if( o & (1 << k) ) continue; //k已經放了 91 if( p[k] != -1 && p[k] != i ) continue; //k被固定了 92 if( have[i] != -1 && have[i] != k ) continue; //位置i被固定了 93 nt = o | (1 << k); 94 //printf(" i = %d o = %d k = %d nt = %d\n",i,o,k,nt); 95 for(int pr = 0;pr < n;pr++){ 96 if( (o & (1 << pr ) ) == 0) continue; //pr不在o里 97 if( dp[o][pr] == -inf ) continue; 98 //printf(" i = %d o = %d k = %d nt = %d pr = %d\n",i,o,k,nt,pr); 99 dp[nt][k] = max(dp[nt][k],dp[o][pr] + a[pr] * a[k]); 100 } 101 } 102 } 103 } 104 /* 105 for(o = 0;o < tot;o++){ 106 for(i = 0;i < n;i++){ 107 printf(" o = %d i = %d dp = %I64d\n",o,i,dp[o][i]); 108 } 109 }*/ 110 for(i = 0;i < n;i++){ 111 ma = max(ma,dp[tot - 1][i]); 112 } 113 printf("Case #%d:\n",ccnt); 114 printf("%I64d\n",ma); 115 } 116 117 return 0; 118 }

?

轉載于:https://www.cnblogs.com/njczy2010/p/5515788.html

總結

以上是生活随笔為你收集整理的hdu 5691 Sitting in Line的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。