首页 > 代码库 > zoj3471（状压dp）
zoj3471（状压dp）
题目连接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=4257
题意：不超过10种气体，两两之间相互碰撞可以产生一定的能量，如a碰b，那么b气体就消失，自身不能碰自身，问最后所能得到的最大能量。
分析：用10位二进制表示气体是否存在，0表示存在，1表示不存在，s（上一个状态）中的两种气体碰撞并且有一种消失，可以得到新的状态进行状态转移。
转移方程：dp[s|(1<<(j-1))]=max(dp[s|(1<<(j-1))),dp[s]+a[i][j]).
#include <cstdio>#include <cstring>#include <string>#include <cmath>#include <iostream>#include <algorithm>#include <queue>#include <cstdlib>#include <stack>#include <vector>#include <set>#include <map>#define LL long long#define mod 100000000#define inf 0x3f3f3f3f#define eps 1e-9#define N 100010#define FILL(a,b) (memset(a,b,sizeof(a)))#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1using namespace std;int a[15][15];int dp[1200];int main(){ int n; while(scanf("%d",&n)&&n) { for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) scanf("%d",&a[i][j]); FILL(dp,0); for(int s=0;s<(1<<n);s++) { for(int i=1;i<=n;i++) { if(s&(1<<(i-1)))continue; for(int j=1;j<=n;j++) { if(i==j||(s&(1<<(j-1))))continue; dp[s|(1<<(j-1))]=max(dp[s|(1<<(j-1))],dp[s]+a[i][j]); } } } int ans=0; for(int i=0;i<(1<<n);i++) ans=max(ans,dp[i]); printf("%d\n",ans); }}
zoj3471（状压dp）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。