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("%lldn",ans); 62 } 63 return 0; 64 }
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/605399.html