给出一个n 代表n个数 每个数有 v（代表数的值) pos(代表数的位置 -1表示任意位置）
要求将这n个数进行排列 使得不违背位置关系
求所有相邻两个数乘积和的最大值
dp[i][j] i表示上一个用的是编号为i的数 j表示状态（这个状态表示不是表示该位置填了数 而是表示该编号的数已经用掉了
#include<bits/stdc++.h> using namespace std; //input by bxd #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i>=(b);--i) #define RI(n) scanf("%d",&(n)) #define RII(n,m) scanf("%d%d",&n,&m) #define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k) #define RS(s) scanf("%s",s); #define ll long long #define pb push_back #define REP(i,N) for(int i=0;i<(N);i++) #define CLR(A,v) memset(A,v,sizeof A) ////////////////////////////////// #define inf 0x3f3f3f3f const int N=20; int getnum(int x) { int cnt=0; while(x) { cnt+=x&1; x>>=1; } return cnt; } int a[N],p[N]; int n; int dp[N][1<<N]; int main() { int kase=0; int cas;RI(cas); while(cas--) { RI(n); rep(i,0,n-1)RII(a[i],p[i]); rep(i,0,n-1) rep(j,0,(1<<n)-1) dp[i][j]=-inf; rep(i,0,n-1) if(p[i]==-1||p[i]==0) dp[i][1<<i]=0; rep(sta,0,(1<<n)-1) rep(i,0,n-1)//前一个 if(dp[i][sta]>-inf) rep(j,0,n-1) if(p[j]==-1||p[j]==getnum(sta)) { if(sta&(1<<j))continue; if(i==j)continue; int now=sta|(1<<j); dp[j][now]=max(dp[j][now],dp[i][sta]+a[j]*a[i]); } int ans=-inf; rep(i,0,n-1) ans=max(ans,dp[i][(1<<n)-1]); printf("Case #%d: ",++kase); cout<<ans<<endl; } return 0; }