hdu5691 Sitting in Line（状压dp）

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<cmath>
 6 using namespace std;
 7 #define max(a,b) a>b?a:b
 8 #define ll long long
 9 #define inf 0x3f3f3f3f
10 int a[20], b[20], num[1<<16];
11 ll dp[20][1<<16]; // dp[x][y]  x表示数组最后一个元素，y表示当前状态
12 int n;
13 int getnum(int x){
14     int ret=0;
15     while(x){
16         ret++;
17         x=x&(x-1);
18     }
19     return ret;
20 }
21 void init(){
22     for(int i=0;i<(1<<16);++i)
23     num[i]=getnum(i);
24 }
25 int main()
26 {
27     int t, i, j, k, cas=1;
28     init();
29     scanf("%d",&t);
30     while(t--){
31         scanf("%d",&n);
32         for(i=0;i<n;++i)
33             scanf("%d%d",&a[i],&b[i]);
34         for(i=0;i<n;++i){
35             for(j=0;j<(1<<n);++j)
36                 dp[i][j]=-inf;
37         }
38         for(i=0;i<n;++i){
39             if(b[i]==-1||b[i]==0)
40             dp[i][1<<i]=0;
41         }
42         for(i=1;i<(1<<n);++i){
43             for(j=0;j<n;++j){
44                 if(i&(1<<j)==0) continue;
45                 if(dp[j][i]==-inf) continue;
46                 for(k=0;k<n;++k){
47                     if(j==k) continue;
48                     if(i&(1<<k)) continue;
49                     if(b[k]==-1||b[k]==num[i]){
50                         dp[k][i|(1<<k)]=max(dp[k][i|(1<<k)],
51                         dp[j][i]+a[j]*a[k]);
52                     }
53                 }
54             }
55         }
56         ll ans=-inf;
57         for(i=0;i<n;++i){
58             ans=max(ans,dp[i][(1<<n)-1]);
59         }
60         printf("case #%d:\n",cas++);
61         printf("%lld\n",ans);
62     }
63     return 0;
64 }