poj2288
TIP： 注意分析好状态，这里用一个三维的数组表示，注意要另外开一个num数组。 n=1时候要注意特判。
#include<cstdio> #include<vector> #include<cstring> #include<algorithm> using namespace std; typedef long long ll; int n,m; ll v[20]; int mp[20][20]; ll val,cnt; ll dp[1<<13][20][20]; ll num[1<<13][20][20]; int main() { int T; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); for(int i=0;i<n;i++) { scanf("%lld",&v[i]); } memset(mp,0,sizeof mp); // for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { int a,b,c; scanf("%d%d",&a,&b); a--; b--; mp[a][b]=mp[b][a]=1; } } if(n==1) { printf("%lld 1\n",v[0]); continue; } memset(num,0,sizeof num); memset(dp,-1,sizeof dp); for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { if(i!=j&&mp[i][j]) { dp[(1<<i)+(1<<j)][i][j]=v[i]*v[j]+v[i]+v[j]; num[(1<<i)+(1<<j)][i][j]=1; } } } for(int i=0;i<(1<<n);i++) { for(int j=0;j<n;j++) { if(i&(1<<j)) for(int k=0;k<n;k++) { if((i&(1<<k))&&(mp[j][k])&&j!=k) for(int t=0;t<n;t++) { if(i&(1<<t)) continue; if(j!=t&&k!=t&&mp[k][t]) { int ne=i+(1<<t); if(dp[i][j][k]==-1) continue; int tmp=dp[i][j][k]+v[k]*v[t]+v[t]; if(mp[j][t]) { tmp+=v[t]*v[j]*v[k]; } if(tmp>dp[ne][k][t]) { dp[ne][k][t]=tmp; num[ne][k][t]=num[i][j][k]; } else if(tmp==dp[ne][k][t]) { num[ne][k][t]+=num[i] [j][k]; } } } } } } val=-1; cnt=0; for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { if(i==j) continue; if(dp[(1<<n)-1][i][j]>val) { val=dp[(1<<n)-1][i][j]; cnt=num[(1<<n)-1][i][j]; } else if(val==dp[(1<<n)-1][i][j]) { cnt+=(num[(1<<n)-1][i][j]); } } } if(val!=-1) printf("%lld %lld\n",val,cnt/2); else puts("0 0"); } return 0; }