题意：
有n种化学物质，他们彼此反应会有一种消失并释放出能量。
给出矩阵，第i行j列代表i和j反应j消失释放的能量。
求最大释放多少能量。
思路：
状态压缩DP，我是这么想的。
利用二进制0代表该物质还存在，1代表不存在。
那么一共有2^(n)种状态，每个状态都视为从上一个状态发生一次反应少了一种物质。枚举可能少的物质。
这题被自己坑了，其实不是2^(n)种状态，因为无论如何都会剩一种物质，并不是所有的物质都会消失。所以状态的总数是2^(n)-1种，然后从所有的剩一种物质的状态中寻找max。就是答案。
#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; const int inf=0x3f3f3f3f; int pho[12][12]; int dp[1<<12]; int main() { int n; scanf("%d",&n); while(n) { int ans=-inf; for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { scanf("%d",&pho[i][j]); } } for(int i=1;i<(1<<n);i++) { dp[i]=-inf; } int num; for(int s=0;s<(1<<n);s++) { num=0; for(int i=1;i<=n;i++) { if(s&(1<<(i-1))) { if(s==(1<<(i-1))) { for(int j=1;j<=n;j++) { if(i==j) continue; dp[s]=max(dp[s],pho[j][i]); } } else { for(int j=1;j<=n;j++) { if((s&(1<<(j-1)))==0) { dp[s]=max(dp[s],dp[s^(1<<(i-1))]+pho[j][i]); } } } } else { num++; } } if(num==1) { ans=max(ans,dp[s]); } } printf("%d\n",ans); scanf("%d",&n); } }
原文：http://www.cnblogs.com/tun117/p/4943666.html