Most Powerful(ZOJ 3471状压dp)

题意:n个原子,两两相撞其中一个消失,产生能量,给出任意两原子相撞能产生的能量,求能产生的最大能量。

分析:dp[i]表示情况为i时产生的最大能量

/*#include <map>
#include <set>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <string>
#include <cctype>
#include <complex>
#include <cassert>
#include <utility>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
typedef pair<int,int> PII;
typedef long long ll;
#define lson l,m,rt<<1
#define pi acos(-1.0)
#define rson m+1,r,rt<<11
#define All 1,N,1
#define read freopen("in.txt", "r", stdin)
const ll INFll = 0x3f3f3f3f3f3f3f3fLL;
const int INF= 0x7ffffff;
const int mod = 1000000007;
int n,dp[2000],a[15][15];
void solve(){
memset(dp,0,sizeof(dp));
for(int i=(1<<n)-1;i>0;--i){
int maxv=0,m=i;
for(int j=0;j<n;++j){
if((m&1)==0){
int maxp=0,t=i;
for(int k=0;k<n;++k){
if((t&1)&&a[k][j]>maxp)
maxp=a[k][j];
t>>=1;
}
if(dp[i^(1<<j)]+maxp>maxv)
maxv=dp[i^(1<<j)]+maxp;
}
m>>=1;
}
dp[i]=maxv;
}
int maxpow=-1;
for(int i=0;i<n;++i){
if(maxpow<dp[(1<<i)])
maxpow=dp[(1<<i)];
//cout<<dp[(1<<i)]<<endl;
}
printf("%d\n",maxpow);
}
int main()
{
while(~scanf("%d",&n)){
if(n==0)break;
for(int i=0;i<n;++i)
for(int j=0;j<n;++j)
scanf("%d",&a[i][j]);
solve();
}
return 0;
}*/
//
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <string>
#include <cctype>
#include <complex>
#include <cassert>
#include <utility>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
typedef pair<int,int> PII;
typedef long long ll;
#define lson l,m,rt<<1
#define pi acos(-1.0)
#define rson m+1,r,rt<<11
#define All 1,N,1
#define read freopen("in.txt", "r", stdin)
const ll INFll = 0x3f3f3f3f3f3f3f3fLL;
const int INF= 0x7ffffff;
const int mod = 1000000007;
int dp[1100],n;
int power[15][15];
void solve(){
memset(dp,0,sizeof(dp));
int cas=(1<<n);
for(int i=0;i<cas;++i)
for(int j=0;j<n;++j){
if((i&(1<<j)))continue;
int maxv=-1;
for(int k=0;k<n;++k)
if((i&(1<<k))==0&&j!=k)
dp[i|(1<<j)]=max(dp[i|(1<<j)],dp[i]+power[k][j]);
}
int maxv=-1;
for(int i=0;i<cas;++i)
maxv=max(maxv,dp[i]);
printf("%d\n",maxv);
}
int main()
{
while(~scanf("%d",&n)){
if(n==0)break;
for(int i=0;i<n;++i)
for(int j=0;j<n;++j)
scanf("%d",&power[i][j]);
solve();
}
return 0;
}

  

上一篇:U3D使anim,unity,prefab文件不显示乱码


下一篇:mysql count max min 语句用法