[状态压缩DP]zoj 3471：Most Powerful

大致题意：

    有n颗原子，给出一个n*n的矩阵map。map[i][j]=a，则代表第i个原子和第j个相撞，且第j个原子会消失，并且释放出a的能量，现在求释放能量的最大值是多少。

 

大致思路：
    dp[b]表示状态b下的最大能量值，比如b=10，则可以二进制转化为1010，在这里我们把0看作保留这一位的原子，1看作这一位的原子消失。则dp[10]可看作第2，4位的原子消失，其他位的原子保留时能量释放的最大值。

由题意可以得到状态转移方程 dp[i+pw[j]]=max(dp[i]+map[k][j],dp[i+pw[j]]);

这里pw[]为：1，2，4，8……

 

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int pw[11]={1,2,4,8,16,32,64,128,256,512,1024};
int map[20][20];
int dp[2000];
int main(){
	int i,j,k,ans,n;
	while(cin>>n&&n){
		for(i=0;i<n;i++){
			for(j=0;j<n;j++){
				cin>>map[i][j];
			}
		}
		ans=0;
		memset(dp,0,sizeof(dp));
		for(i=0;i<pw[n];i++){
			for(j=0;j<n;j++){
				for(k=0;k<n;k++){
					if(((i&pw[j])==0)&&((i&pw[k])==0)&&j!=k){
						dp[i+pw[j]]=max(dp[i]+map[k][j],dp[i+pw[j]]);
						ans=max(ans,dp[i+pw[j]]);
					}
				}
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}