题意：两个原子如果碰撞会释放出相应的能量，并且其中有一个原子碰撞后会湮灭。
求所有碰撞状态中释放出的能量的最大值。
分析：由于最多只有10个原子，所以可以用二进制枚举所有状态，二进制位上为1表示
该原子已经湮灭。0表示还没有。
dp方程： dp[i]表示i状态下得到的最大能量。
dp[i|tmp]=max(dp[i|tmp]，dp[i]+mp[k][j])；
dp[i]+mp[k][j]表示 第j个原子和第k个原子碰撞，第j个原子湮灭产生的能量。
tmp是由i上转移过来的，tmp=i|(1<<j)。
#include<cstdio>
#include<iostream>
#include<cstring>
#define maxn (1<<10)
using namespace std;
int dp[maxn],mp[15][15];
int maxx(int x,int y)
{
return x>y?x:y;
}
int main()
{
int n,tot,tmp,ans;
while(scanf("%d",&n)!=EOF)
{
if(n==0) break;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
scanf("%d",&mp[i][j]);
}
}
memset(dp,0,sizeof(dp));
tot=(1<<10);
for(int i=0;i<tot;i++)
{
for(int j=0;j<n;j++)
{
int tmp1=(1<<j);
if((i&tmp1)==0)
{
for(int k=0;k<n;k++)
{
int tmp2=(1<<k);
if((i&tmp2)==0 && j!=k)
dp[i|tmp1]=maxx(dp[i|tmp1],dp[i]+mp[k][j]);
}
}
}
}
ans=0;
for(int i=0;i<tot;i++)
{
if(dp[i]>ans)
ans=dp[i];
}
printf("%d\n",ans);
}
return 0;
}
也可以用个数组把所有状态存起来方便用。
即把10个位置每个原子湮灭的状态表示在数组state中。
#include<cstdio>
#include<iostream>
#include<cstring>
#define maxn (1<<10)+10
using namespace std;
int dp[maxn],mp[15][15];
int state[11]={1,2,4,8,16,32,64,128,256,512,1024};
int maxx(int x,int y)
{
return x>y?x:y;
}
int main()
{
int n,tot,ans;
while(scanf("%d",&n)!=EOF)
{
if(n==0) break;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
scanf("%d",&mp[i][j]);
}
}
memset(dp,0,sizeof(dp));
for(int i=0;i<state[n];i++)
{
for(int j=0;j<n;j++) //枚举每一个原子
{
if((i&state[j])==0) //如果这个原子还没被湮灭
{
for(int k=0;k<n;k++) //则找另一个还没湮灭的原子于j原子碰撞
{ //使j原子湮灭
if((i&state[k])==0 && j!=k)
dp[i|state[j]]=maxx(dp[i|state[j]],dp[i]+mp[k][j]);
}
}
}
}
ans=0;
for(int i=0;i<state[n];i++)
{
if(dp[i]>ans)
ans=dp[i];
}
printf("%d\n",ans);
}
return 0;
}